• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
ontheheap

Why use a Linked List?

16 posts in this topic

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?
0

Share this post


Link to post
Share on other sites
im no expert on this topic, but..

i believe lists are the best data structure to use when you are doing inserts and deletes from the middle (or either end) of the container.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
Keeping track of a bullet might be used by a LL. I used one for linking flash cards together since the user is the only person that will know how many cards they need.
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
okay,

LL over DA other then what has been mentioned already.

Memory consuption and fragmentation.
LL are optimal for constantly changing datasets because they only use the memory that they need. Also they don't need to use any "realloc"'s to grow or shrink.

STL while fast (in most cases) will evntually have to do a realloc. this will take time and probably leave a large whole in memory.

DA are mostly the same.

LL (more so Double LL) can easly be turned into a binary tree.
Making searching on a key, very quick.


Personal Experience.
The engine I'm writting for work, uses a node system (read double linked list with parent and child relation ships). arrays would be nice, but the memory were saving here will be used forr more polys.

0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
there's no std implementation, but u may want to try creating chunked linked lists, which are a hybrid between linked lists and dynamic arrays: you link chunks of dynamic arrays that are the same size, works a lot like the hard drive file systems
you allocate a block that can contain 32 elements (just an example) and when u fill up all those elements, you allocate another block and link it to the end
doing that, you can increase your list traversal speed to to almost match that of a dynamic array, but i should caution you, IT IS EXTREMELY HARD TO CREATE A RELIABLE CHUNK LINKED LIST THAT SUPPORTS INSERT AND REMOVE WITH MINIMAL MEMORY WASTE OR CPU USE
other than that, pushing, popping elements and traversing the list WILL be much faster than an ordinary linked list


edit: removal can be done easily by moving the last element in a chunk, to the position of the removed,
0

Share this post


Link to post
Share on other sites
Another thing to mention is the linked lists are a very old technique which was extremly usefull befor computers got very fast and had heaps of memory. Things like .NET, Java, and to a less extend the STL which allow you to have dynamic arrays are relativly new. If you were programming something in the 1980's then you either had to write your own dynamic array code or use a linked list. Both take about the same time to impliment but for the memory concious 1980's style programmer linked lists are definatly the better option in many situations (as has been said when deleting and inserting happens alot). Linked lists are still very handy today in all the areas stated, I'm just pointing out that historically they were quite important where as today we have more options.

EDIT: Added the word "impliment" to clear things up

[Edited by - kaysik on January 11, 2005 7:18:14 PM]
0

Share this post


Link to post
Share on other sites
Quote:
Original post by kaysik
Another thing to mention is the linked lists are a very old technique which was extremly usefull befor computers got very fast and had heaps of memory. Things like .NET, Java, and to a less extend the STL which allow you to have dynamic arrays are relativly new. If you were programming something in the 1980's then you either had to write your own dynamic array code or use a linked list. Both take about the same time but for the memory concious 1980's style programmer linked lists are definatly the better option in many situations (as has been said when deleting and inserting happens alot). Still linked lists can be very handy in all the areas stated, I'm just pointing out that historically they were quite important where as today we have more options.


dude, wtf r u smoking? .net and java's dynamic arrays ARE slower than C++'s linked lists plus if u wonna insert an object at the beginning of a dyn array, u wuld have to MOVE the entire array whereas with a linked list all u have to do is create a new container and update a couple mem addresses
0

Share this post


Link to post
Share on other sites
Quote:
Original post by caesar4
.net and java's dynamic arrays ARE slower than C++'s linked lists

They're entirely different structures with different algorithmic complexity. Your comparison makes no sense. Compare Java's and .NET's linked list implementation against C++'s, or compare their dynamic arrays against std::vector.

Quote:
plus if u wonna insert an object at the beginning of a dyn array, u wuld have to MOVE the entire array whereas with a linked list all u have to do is create a new container and update a couple mem addresses

Certainly, that's one of the advantages of a linked list. It has disadvantages, however, such as the O(n) access time for elements not at either end.
0

Share this post


Link to post
Share on other sites
Quote:

dude, wtf r u smoking? .net and java's dynamic arrays ARE slower than C++'s linked lists plus if u wonna insert an object at the beginning of a dyn array, u wuld have to MOVE the entire array whereas with a linked list all u have to do is create a new container and update a couple mem addresses


Caesar

I think that has to be the most ignorant comment I've ever seen on this board. Perhaps you should apply your high power of perception to an Algorithm textbook before you post anything else about data structures. Not everyone uses a data structure to merely insert data. Every now and then people get this crazy idea of using the information they want to store and for that (as already mentioned in previous posts) is O(1) time. Like Miserable said they're two different data structures and if you re-read this entire thread you'll see times when using each would be useful.

What kaysik said was the kind of thing I come to this board to learn. All he was doing was offering his insight in a public forum and nothing which he said was wrong.
0

Share this post


Link to post
Share on other sites
Quote:
Original post by caesar4
dude, wtf r u smoking? .net and java's dynamic arrays ARE slower than C++'s linked lists plus if u wonna insert an object at the beginning of a dyn array, u wuld have to MOVE the entire array whereas with a linked list all u have to do is create a new container and update a couple mem addresses


did you read my post? No where did I compare .net or java's dyamic arrays to c++'s linked lists ... my point was that historically linked lists were used in situations where now we have other options. If you were refereing to my comment "Both take about the same time but for the ..." then you misunderstood what I meant - my point was "Both take about the same time to IMPLIMENT but for ....", as in writing array code vs writing LL code isn't much different in terms of difficulty, but if you have 16k of memory you'll definatly choose linked lists instead of wasting mem on an array (if it fits the situation of course).
0

Share this post


Link to post
Share on other sites
Quote:
Original post by caesar4
there's no std implementation, but u may want to try creating chunked linked lists, which are a hybrid between linked lists and dynamic arrays


Am I wrong, or is that how deques are implemented?
0

Share this post


Link to post
Share on other sites
Hi all,

I do reimplement linked-link to learn how exactly they work. It'll be helpful to learn how iterators work too for it'll increase the performance of the linked list for iteration.

I also believe that linked-list concept is a stepping stone to all other types of storage containers like hashtable, hashmap, map, tree and so on...

Afterall, we thought of using linked-list all because the use of arrays are way too troublesome and nasty most of the times. And things like trees and hashmaps came out to improve performance for object-search-and-get functions. I'm not sure if the original concept is derived from linked-list but I'm sure learning LL does help.

Using STL's storage algos is an easy way out having all the different types of containers suited for different purposes written nicely. However, to really use it properly and efficiently, you'll need to understand how it works logically.

Happy developing!!
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0