Linked Lists

[Radical Raccoon]

If you have a game consisting of a large particle/projectile/enemy system, then a linked list would be the more efficient way of handling those. You can effeciently delete the object with just a couple lines of code executing. No loops or shuffling or whatever to fill in the empty space with a static/dynamic array. That eats up alot of time-the bigger the array the longer it takes to remove the object. With a linked-list it takes virtually the same amount of time no matter what.

[relsoft]

They(Lists) are a lil slower than arrays though.

[helium]

Whether to use linked lists or vectors depends very much on the operations you normaly perform.

Indexed access is way faster on vectors. As good sort-algorithms (quicksort, heapsort, mergesort) need indexed access, sorting vectors is normaly faster than sorting linked lists.

Appending elements to a vector can be fast as well, if you start with more memory than needed and resize by 2 (or 1.5 or whatever) whenever the memory is full. This is used by C++'s std::vector.

If you often need to insert or delete elements in the middle a linked list ist way faster (it has a complexity of O(1) in contrast to an O(n) operation on vectors!!!).


So vectors and linked lists have both their uses.

[Radical Raccoon]

They(Lists) are a lil slower than arrays though.

How? Do you mean by iterating through them?

[relsoft]

Joe: Helium explained very well. Linked lists need a pointer to the next structure and a pointer to the previous struct if its doubly linked. With arrays, all you have to do is get the index. Linked lists are good for small particle engines though.

[Radical Raccoon]

Joe: Helium explained very well. Linked lists need a pointer to the next structure and a pointer to the previous struct if its doubly linked. With arrays, all you have to do is get the index. Linked lists are good for small particle engines though.

Yes, it would take more memory, and you can't instantly access a specific spot on the list without iterating through it, but I don't see how that makes them slower.

Is...

Code:

index = index + 1;
x = array;[index]

faster than...

Code:

object = object->next;
x = object->value;

??

Or did you mean...

Code:

x = array[100];

Is faster than...

Code:

x = linkedlist[100];

In that case it is way faster to access the data with the array, but with a system where you aren't randomly selecting an index all the time I don't see how it would be faster.

[na_th_an]

Linked lists implemented dynamicly with pointers are faster when inserting/removing objects, slower to retrieve data from them. Linked lists implemented staticly with arrays are slower when inserting/removing objects, faster to retrieve data from them.

Why?

Insert/Delete element: In linked lists with pointers you just take in or out the element and connect a couple of pointers. In statics lists with arrays you have to rearrange the items in the list, which is slower.

Get data: In linked lists with pointers you have sequential access and have to jump step by step to element #n, while in static lists using arrays you can access the nth element directly, which is faster.

-

The best pick depends on the problem. If you are inserting/deleting way more than getting the value you want the dynamic with pointers approach.