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

## Recommended Posts

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

##### Share on other sites
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:

#include <vector>using namespace std;#include <stdio.h>#include <stdlib.h>#include <time.h>int main(void){	srand(time(NULL));	vector<int> vecList;	for (int i = 0; i < 10; i++)	{		int num = rand()%100;		printf("(Add..) #%d: %d\n", i, num);			vecList.push_back(num);	}		vector<int>::iterator IntIt = vecList.begin();	int i = 0;	for (IntIt = vecList.begin(); IntIt != vecList.end(); IntIt++)	{		int num = (*IntIt);		printf("(Print) #%d: %d\n", i++, num);	}		system("pause");}

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'.

##### Share on other sites
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?

##### Share on other sites
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?

##### Share on other sites
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)

##### Share on other sites
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.

Thanks!

##### Share on other sites
linked list are good in games when you need to divide up a world, collison detection between objects means loop through the entire list, usally many times per frame, so for a big map it makes sense to have a grid of lists so you only need to test agenst a small amount of the map but since sprites may move between grid areas you need a low add/remove cost

##### Share on other sites
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.

##### Share on other sites
I just don't know why this is in the game design forum and not the programming forum

• 10
• 16
• 14
• 18
• 15