When is a good time to use Linked Lists and when is a bad? For instance, if I am coding a GBA game and I know that it's unlikely there'll be more than 10 enemies in the vicinity at a time but there could also be 0... Is it a better idea to just create an array of 10 enemies and leave some unused? Or use a Linked List? How slow are Linked Lists compared to simple arrays? (my functions are very basic and simple, infact they're almost identical to the ones out of TOTWGPG as that's where I learnt to use Linked Lists. ------- Spadge. [edited by - spadge on February 18, 2003 3:36:11 PM]

Arrays use more memory(if you''re not using all of it), but it''s VERY fast for accessing a specific element. On the other hand it''s very slow to add/move an element.

Lists only use as much memory as nodes you have & adding/deleting/moving nodes is very fast. Accessing is slower however as you much traverse from the head until you find the node you''re looking for.

You've got to think about the prons and cons of linked lists. Pro, they are completely changeable in size. Con, they a DAMN slow. So if you can't get away with it anyother way then use them. Otherwise if you need speed as a requirement and changeable sizes isn't criticle then use arrays.


EDIT: Damn, that AP could type faster than me

[edited by - RamboBones on February 18, 2003 3:44:10 PM]

Well if you take a look at what a linked list is you''ll notice the following.

#1 Linked lists allocate and delete memory when elements are added or removed from the list.

#2. Because of the design you can''t just go to element #4 you have to start off at element #1 goto element #2, then element #3 and finally hit element #4.


#3. Linked lists can go on forever (or until you run out of memory).

Now lets look at an array

#1. Arrays don''t go on into infinity they are size limited, although you can dynamically allocate more memory for the array and extend it''s size.

#2. Arrays allow you to access any element in the array at any time 1, 5, 655, in any order you want.


Now in games typically you don''t want to be allocating or deallocating memory while the user is playing the game. This is limited to "Loading..." screens. So more often than not a linked list will not be the choice you make because it always does a new and delete which is very slow. That said, you''d use a list when you have no need for randomly accessing elements in the list or array. If it''s always going to be in forward or reverse order than a list is perfect. Otherwise you''ll want to use a dynamic array because it provides faster access to the elements than you get with a list.