I'm sure LLs have their uses. However, I can't think of a place where they would be better suited than, say, a dynamic array. The book "Data Structures for Game Programmers" gives an example of using a dynamic 2d array of single linked lists so that each tile in a 2d game can have any number of layers. Now, I see how this can save memory (since each tile only has as many layers as it will use). Is this beneficial in practice, and not just in theory? There's more overhead when dealing with a linked list, and checking the "status" of a specific tile/layer will take longer than if I used an array. Why not just have a dynamic 2d array of dynamic 1d arrays? I guess I'm just not getting the benefit of using a linked list. So, any personal experiences with using a linked list in a game, where a list was actually better suited than any other data structure?

I used a linked list when I wrote my Half-life level viewer. I used it to store the entities (worldspawn etc). This was written in C, so today I would probably use an STL vector. I didn't know how many entities there were in the file beforehand, so I used a linked list. Each time I read a new entity I added it to the list. I didn't need to be able to quickly locate items in the list because the entities weren't used that frequently.

Some advantages over regular arrays:

- easy to sort (just swap pointers)
- easy to insert/delete items (just change the pointers)

Umm, I can't think of anything else at the moment :) Of course, if you were using C++, it would probably be wiser to use the STL.

For some sort of tile map-based game, I imagine that using a linked list for the layers might not be the best idea because generally you would want to render each layer in order. It would be much faster to have an entire layer in one single array (unless you also collected all the nodes for each layer together somehow, perhaps in a layer array or something).

cheers
sam.

You choose data structures based on your projected usage patterns. If you need fast random access to elements in the sequence, you choose some form of dynamic array. If you need to frequently insert and remove elements at arbitrary positions in the sequence, you choose a linked list. If you only wish to append and remove elements from one end, you choose a stack, which can be implemented as a constrained adaptation of the linked list. Similarly, the queue is an adaptation of the linked list to append to the tail and remove from the head. Both the stack and the queue can be written as adaptations of the deque, though, which is itself an adaptation of the general list concept to support addition and removal of elements at either end of the sequence, but not in the middle (the name "deque" stands for "double-ended queue").

These assertions are supported by algorithmic analysis of the number of steps required to perform each operation for each data structure as a function of the number of elements in the structure. Optimal performance is O(1), meaning that the time required is constant, regardless of the number of elements in the sequence. Random access in an array, then, is O(1). O(n) would mean the time required is directly proportional to the number of elements in the sequence: list node insertion and removal is O(n). In contrast, array element insertion and removal is O(n²), because of the overhead of copying each element from the point of insertion to the end of the sequence one place over. In ever situation, you want to minimize the magnitude of the value within the parentheses.

A data structures course or text will provide you with detailed instruction in all of these comparisons and analyses, better enabling you to make informed decisions as to what data structure to employ in which situation.

I'm sure there are tons of applicable uses - such as if you have to have a sorted list of large structures - then you can easily insert and delete without having to reallocate memory or move things around.

I think the real uses of LL's come in with Hash Tables (I think that is what I'm thinking of but I may be wrong). The bucket and chain method is where having a LL is most useful - since each bucket can have any number of chains. A practicle example would be lets say you have a telephone directory that alphabetizes by the first 2 characters of the last name. SM with have more entries than ZZ would - thus making the LL appraoch very benefitial and space saving.

As for games, I do not think that linked lists have as much use in games - from my own experience. With the STL classes, you can achieve the theorey of LL without all the extra hassals.

Quote:Original post by Drew_Benton
With the STL classes, you can achieve the theorey of LL without all the extra hassles.

You do realize that the std::list is a templated implementation of a linked list, right?

Alright, so this is basically just another variant of the "which language should I learn" question! It doesn't make sense to store data in a LL if I need (semantics aside) random access, but if I know I'll be inserting/removing elements (nodes) then a LL would make more sense than, say, a dynamic array. Choosing the right data structure for the task is what's important. The first chapter of the book was a very brief intro to algorithm analysis, so I do understand what is meant by the big-o notation (O(1), 0(log n), 0(n^2), etc). I also see that when I'm finished with this book I need to learn how to use the STL. I do want to learn how things work, but I certainly don't want to reinvent the wheel every time I start a new project.