Jump to content
  • Advertisement
Sign in to follow this  
Gink

How often are linked lists used in games?

This topic is 4798 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 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
If I can, I use the standard std::list in C++. If I can't, I'll write my own templated one.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!