Hello, is there any use for linked lists or double-linked lists in gamedesign? (Just asking, for no particular reason.)

Absolutely. Though, instead of writing your own, you might consider using a library such as the popular STL (Standard Template Library). You've got loads of different container types, and you needn't worry about dealing with pointers and whatnot.

An example of a list of integers would be:



As for their actual use, it would be beneficial to have a simple, fast, and well-tested method of creating lists of resources in a game engine, whether these are bitmaps, sounds, models, window/GUI elements, network connections, or pretty much anything else you can think of which exists in a 'list'.

Hm. No. You are thinking at the wrong level: linked lists are an implementation detail, a data structure. They won't play a direct role in game design.

However, having sufficient knowledge of data structures (there are many, many more than just linked lists, you know) and related algorithms is fundamental to knowing what is easy, what is feasible, and what is not.

You wouldn't want your game to hinge on solving a known impossible problem, would you?

I know a little about data structures (not very much though). Vectors are very useful, efficient and heavily used, but how about linked lists? I guess, there are situations where dynamic-sized containers - like linked lists - might come in handy, but when? And, in that case, what kind of linked lists?

When you need a list. When you don't need fast random access (Linked lists have O(n) where vectors are O(1)), when you need to be able to insert/remove from the middle of the list (Hard to do with a vector without completely copying it)

Lists are used a lot, such as for dynamic object lists (missles in flight, targets, etc).

You wouldn't usually want to use a map or vector for highly dynamic "lists", because the insertion / growth cost is a little too high. although truthfully, if there will never be any dependence on order (no sorting, no rearanging based on movement, etc) and there is a reasonable maximum, then a vector would work in place of a list just fine .. but as soon as items need to move in the list, a vector sucks (cause to get item F to the front of the list, items A-E have to be moved back).

I use:

std::list
std::vector
std::deque
std::map

and a few custom containers as well.

I got some useful answer!
Thanks!

Fruny is right. Data structures are what you need to think about when you're actually trying to implement the game design.

Game Design is a much higher (more abstract) plan for what the game is all about. I actually think that the title of the forum should be changed to "Game Ideas" or even "Game Analysis", because in software engineering lingo, the term design has a more rigid definition. Game Ideas is actually what this forum is really about....discussing the ideas of gameplay.

Now, data structures and algorithms combined ARE your program. And data structures and algorithms mutually affect each other. What data structure you use determines what algorithms you can use, and vice versa.

Linked Lists (whether you're talking about singly linked lists, doubly linked lists, sentinel lists, or even directed graphs....acyclic or otherwise) are good for when you have to do a lot of inserting or deleting. Just assign the pointers on all the affected nodes to the new node you want, or if you want to delete a node, just point them to null or the next->next node in the link (and don't forget to destroy the deleted node). In a sorted array or vector, whenever you insert or delete a new node, you will have to shift on average n/2 nodes to account for the new or lost node but with a linked list, you need only worry about the adjacent nodes to which you insert and delete. However, searching for a certain node is a linear search, and thus not very good. Though really, that depends on how you implement your list.

Another way to think of a linked list is simply as a way of connecting node objects, the node objects holding pointers or references to other nodes. A tree is really a type linked list. A binary tree for example starts with a root node which has two pointers. These pointers point to two other "leaf" node objects. These two leaf node objects in turn point to their own 2 leaf (or child) node objects. Now searching is much more convenient if we can order the nodes (now we can search in log 2 N time). Directed graphs are also a kind of linked list, where you can think of a node object as a vertex, and every edge on the vertex is a pointer to the next vertex. We tend to think of linked lists as "chains", but that's not how they need be implemented if you roll your own. It's just that most people automatically assume the STL linked list when you say "linked list".

So understanding more than just the STL linked list will greatly help you in understanding how to roll your own data structures, as well as conceptualize how the data is organized.

I just don't know why this is in the game design forum and not the programming forum

Quote:

Original post by lightblade I just don't know why this is in the game design forum and not the programming forum

The question revealed a misunderstanding of both game design and data structures. I strove to provide an answer rather than move the thread to the "obvious" forum, where it would have received the "obvious" answer. I hope he learned more that way.