Where would you use linked lists in a game?

[Pickzell]

I don't know they just seem kind of useless to me.

[Bakkon]

If they seem useless to you, then you obviously haven't read enough about them. Vectors and Lists from the C++ STL are both linked lists. My recent game stored everything in a vector to update and render each individual object. Then special lists were created on the side to keep track of each object's collision list. Go read up on them. They're the absolute polar opposite of useless.

Sorry, this needs to be done:

I don't know they just seem kind of useless to me.

LOLWUT?

[programmerinprogress]

They're very useful, now buy a book!

I find them useful for storing pointers to objects, there's a hell of a lot of things you can do with pointers in games, and other applications, having a means of storing objects dynamically can save a lot of headaches compared to say, a dynamic array, which can be difficult to manage, especially when you need to add more elements on the fly, it just can't be done, you have to reallocate the memory again, but STL containers or just gold 'ol homemade linked lists allow you to simply 'snap on' or remove elements you don't need anymore and you can just delete them from memory.

starting to see why linked lists could be used in a game?

[wacko]

So I think everything said so far is valid in some cases but overall I think the argument for and against a linked list really depends on its use. if your going to index into your list a lot then I would not use a linked list its slower than a normal array, a lot of Vector Impl actually use arrays because they index a lot. If insertion time matters then a linked list could possible be used as it will insert in many cases much quicker than an array. If deleting items in order or reading in order matters than linked lists are a possible option. I think many cases I find myself using them when order matters right, or f you want to insert into the middle of a list then I would use a linked list, but if otherwise use an array. Also linked lists take more mem in many cases as they have to keep around extra data.

[Falco Girgis]

No offense, but if a linked list seems useless then you have a looooot to learn, child.

[wacko]

No offense, but if a linked list seems useless then you have a looooot to learn, child.

I do not know how often its really needed, I think there are specific cases where order matters and it should be used. Also I would like to comment that the STL Vector is not a linked list. It internally uses an Array to track its members it does not work the same way a linked list does.

[avansc]

linked list are the base of all complex data structures. trees and what not.

[internetfx]

I don't know they just seem kind of useless to me.

Most objects in a typical game will be in a linked list when the number of that type of object is not fixed or limited.

When the number of those objects changes often, or there's no fixed limit to how many would be generated, you may not want to use an array/vector. Unused objects in a vector may waste too much memory.

If you find yourself allocating objects and storing pointers to those in a vector to save memory, and position in the array is not important, you may benefit from a linked list instead. Linked lists also work great for LIFO (last-in-first-out) stacks.

Examples for linked lists:

Objects and geometry
Enemies
Weapon fire
Most particles and temporary objects

Examples for arrays/vectors:

Players
Tiled maps
Inventory

Of course this could vary greatly.

Performance can be a problem for a linked list if you have to find an object in the list, even if it's sorted. For this, you'll probably need to step up to a sorted list such as a tree or associative array.