Having alot of Lists in a program

[ahmedkhalifa]

Hello guys,
I wrote this program today that actually took a whole lot of time. However, i did use alot of lists and arrays(although I dellocated the dynamically allocated arrays and destroyed the list after the program finished running). I ended up with a 500 line code while a friend of mine got i around 400s .My O(n) for the program was rougly o(N^2)though.
So is that a terrible program. One thing to note that having that much lists was the optimum solution when it comes to printing.
Thanks :)

[Hanaka]

So what do you want to do? You expect someone to give you a better solution to beat your friend up?

[ahmedkhalifa]

Not really, it's not about the competition I just want to know if more lists = bad program or not

[3pX8b7Xj]

Simple Code dynamically allocated me

#include<iostream>

using namespace std;

int main()
{
	int num;
	int *aptr;
	cout<<"\nEnter The Size Of Array : ";
	cin>>num;
	aptr=new int[num];
	for(int i=0;i<num;i++)
	{
		cin>>aptr[i];
	}
	
	for(int i=0;i<num;i++)
	{
		cout<<aptr[i]<<" ";
	}
	
	
	delete[]aptr;
	return 0;
}

http://www.cplusplus.com/doc/tutorial/dynamic/

[Golden Lizard]

.My O(n) for the program was rougly o(N^2)though.

So Bachmann-Landau can be either O(N) or O(N^2) (or any other complexity), you can't have both, though I think you may want to say that your worst time complexity is O(N^2). You can't have the same the same code with 2 different complexities.

Now, it depends on what is your program supposed to do, maybe O(N^2) may be actually a good complexity for the task you are trying to accomplish, or maybe it's the worst scenario. It's hard to say without knowing what you are trying to do.

As for lists, if you are retrieving elements from from a known position in the list, which are taking O(n) on a list, those would take O(1) on an array or hash table, that would indeed increase your time complexity by quite an amount. Consider you have to access the nth element from a list m lists. This would have the worst time O(n*m) if you are using lists, while it would take only O(n) from an array. If you are doing lots of searches inside an array or list, you'd get O(n) for linear, but in arrays you can improve this time by doing binary search ( O(log n)) or interpolation search (O(log log n)), but consider if a one time O(n log n) sorting would be worth it time-wise (if you are doing a search only 1 time per array, then you're better off using linear search). Depending on what you want to do, you could use a hash table for O(1) time for searching/retrieving elements, but then you'd have to deal with collisions and it's gonna have problems if you add a lot of elements.

Now for space complexity (as you don't specify which complexity you got O(N^2) ), keep in mind that lists will take more memory than arrays, as lists aren't sequential in memory and you gotta allocate one more pointer for element in the list. Using lists isn't a bad practice by any means, it's a bad practice to use lists where you don't need them and there are way better alternatives.

[ahmedkhalifa]

First off, I would like to apologize for the late reply
My program is a simulation program,
It's supposed to be reading a text file containing enemy information then what I chose to do is enqueue them in a queue, then if the a specific enemy spawn time have came up, the enemy would be spawned in their respective region(dequeue then inserted at end a the linked list)..... (Enemies would die randomly atm, with a maximum of 4 enemies dying together during a time step)..then dead enemies are collected in another list -after being removed from the active(alive) list one - the program would end when all the enemies have died---- Also the dead enemy list should be sorted according to enemy 's health
so I used the following O(N^2) code:

void sortlist(node*&head) { //moves the list into an array to be sorted there then returns the linked list back
	int c = countList(head);
	enemy*arr = new enemy[c];
	node*temp = head;
	for (int i = 0; i < c; i++)
	{
		arr[i] = temp->enemyy;
		temp = temp->next;
	}
	enemy xyz;
	for (int i = 0; i < c - 1; i++)
	{
		for (int j = i + 1; j < c; j++)
		{
			if (arr[i].Health>arr[j].Health)
			{
				xyz = arr[i];
				arr[i] = arr[j];
				arr[j] = xyz;
			}
		}
	}
	destroy(head);
	for (int i = 0; i < c; i++)
	{
		insertatEnd(head, arr[i]);
	}
	delete []arr;
}

Enemy struct:
struct enemy

{
	int ID;		//Each enemy has a unique ID (sequence number)
	int time_step; //The time step of each enemey
	Region region;	//Region of this enemy
	int Health;	//Enemy health
	Type type;	//Paver,Fighter,SHielded fighter
	int reload_period;
	int fire_power;
};