• Advertisement
Sign in to follow this  

How often are linked lists used in games?

This topic is 4619 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How often are linked lists used in games? And for what purpose usually?

Share this post


Link to post
Share on other sites
Advertisement
i hate them so i don't use them

i use dynamically allocated arrays or more often std::vector lists

Share this post


Link to post
Share on other sites
i hate them as well, thats why i was wondering if it was used often =p

Share this post


Link to post
Share on other sites
Linked lists have something of a bad rap in the realm of software development, because of their poor performance in random access. They're primarily used for queues and stacks, but since they can be somewhat inefficient compared to dynamic arrays without a well-written pool allocator, they tend not to be used much even there. That's not to say, however, that a linked list is never the best choice; the ability to delete elements without invalidating other iterators is often extremely useful. Linked lists also show up as part of B+trees and ropes.

Share this post


Link to post
Share on other sites
I can't think of a single program I've written in the last 4 or 5 years that didn't feature a linked list.

Share this post


Link to post
Share on other sites
one that you created, or one that is supplied already?

Share this post


Link to post
Share on other sites
I would guess that most c++ programmers would be using the standard template library list...

Share this post


Link to post
Share on other sites
Where? everywhere. purpose? anything. Spatial subdivisions (tree nodes and branches), scene graphs (well, all that are not exactly linked lists, but related anyhow), lists of things, memory allocation tracker, bits and bobs...

Linked lists are just a way to organise your data, like an array, or other types of linked or unlinked lists. No biggie. They come usually in a template form in C++, to make the syntax easier.

Share this post


Link to post
Share on other sites
The problem with linked lists is their limited functionality -- you can't have reverse iterators with singly linked lists, random access is possible but horribly inefficient, and they must keep lots of book keeping information.

Generally, a dynamic array (e.g. std::vector) is a better choice. It has great random-access support, forward and reverse iterators, and very little extra allocated data.

However, linked lists are very easy to implement. And besides that, there are areas where they are the preferable data structure, such as storing the child nodes of a node in a tree structure. So they're definately not totally lacking in the usage department.

Share this post


Link to post
Share on other sites
A simple "actual use" of linked lists that I'm using in my game is to keep track of all of the enemies on the screen. Once I generate an enemy I add him to my linked list, then I can test for collisions and whatnot every frame by iterating through the list. This is just one example of linked lists, but I use them all the time, and I usually write them all myself each time as it only takes about 5 minutes to do (once you've done it enough times), although I'd probably save myself a lot of time to just write a generic linked list class.

Share this post


Link to post
Share on other sites
I'm going to stick my neck out here and say that the majority of the times a linked list comes in really handy is for building more complicated data structures (such as hash maps, trees, rope, etc.). Which is handy because most of the time someone has already written one of those for you. :)

The times when a 'raw' linked list is suitable, a dynamic array/vector tends to be more helpful.

Share this post


Link to post
Share on other sites
A lot of times you don't need random access. You just want to go through the list linearly. If you ever have a situation where you want a list that you want to iterate through linearly, adding and removing nodes at any point as you go (i.e. the order of the nodes matters), linked lists look pretty good compared to arrays.

Share this post


Link to post
Share on other sites
In a multi-threaded context, list become much more viable because insertions require minimal locking for in-place updates, and are even lock-less in some cases (if you can use an atomic exchange).

As mentioned, you tend to use trees alot in games which are more like a list than like a vector (unless it's a btree, which is a good choice, & then it's both).

Generally speaking, if you need to iterate, a vector is better than a list. If you don't need to perform many middle insertions, then deque is better than a list. So it's a rare case list is the best choice, lots of middle insertions and limited iteration.

There's another special case that comes up; heap-like structures where you use the 'dead' memory to keep track of the available space. On deeply embedded chips you tend to nix memory allocation, so everything is allocated statically and then linked together to facilitate iteration. I’m pretty sure we’re beyond that now with gaming platforms though, as even the Nintendo DS now employs an ARM9 that sports an MMU (sort of begging for memory management).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement