Jump to content

  • Log In with Google      Sign In   
  • Create Account

Why use a Linked List?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 mr_101   Members   -  Reputation: 795

Like
0Likes
Like

Posted 11 January 2005 - 10:04 AM

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?

Sponsor:

#2 graveyard filla   Members   -  Reputation: 583

Like
0Likes
Like

Posted 11 January 2005 - 10:15 AM

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.

#3 izzo   Members   -  Reputation: 347

Like
0Likes
Like

Posted 11 January 2005 - 10:16 AM

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.


#4 Oluseyi   Staff Emeritus   -  Reputation: 1678

Like
0Likes
Like

Posted 11 January 2005 - 10:21 AM

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.

#5 Drew_Benton   Crossbones+   -  Reputation: 1727

Like
0Likes
Like

Posted 11 January 2005 - 10:21 AM

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.

#6 SumDude   Members   -  Reputation: 163

Like
0Likes
Like

Posted 11 January 2005 - 10:25 AM

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.

#7 Oluseyi   Staff Emeritus   -  Reputation: 1678

Like
0Likes
Like

Posted 11 January 2005 - 10:26 AM

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?

#8 Yassim   Members   -  Reputation: 164

Like
0Likes
Like

Posted 11 January 2005 - 10:32 AM

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.



#9 mr_101   Members   -  Reputation: 795

Like
0Likes
Like

Posted 11 January 2005 - 10:37 AM

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.

#10 caesar4   Members   -  Reputation: 100

Like
0Likes
Like

Posted 11 January 2005 - 10:53 AM

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,

#11 kaysik   Members   -  Reputation: 382

Like
0Likes
Like

Posted 11 January 2005 - 11:18 AM

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]

#12 caesar4   Members   -  Reputation: 100

Like
0Likes
Like

Posted 11 January 2005 - 12:32 PM

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

#13 Miserable   Members   -  Reputation: 606

Like
0Likes
Like

Posted 11 January 2005 - 12:38 PM

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.

#14 HughG   Banned   -  Reputation: 116

Like
0Likes
Like

Posted 11 January 2005 - 01:50 PM

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.

#15 kaysik   Members   -  Reputation: 382

Like
0Likes
Like

Posted 11 January 2005 - 01:54 PM

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

#16 Doc   Members   -  Reputation: 586

Like
0Likes
Like

Posted 11 January 2005 - 07:34 PM

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?

#17 Thrawn80   Members   -  Reputation: 140

Like
0Likes
Like

Posted 11 January 2005 - 07:56 PM

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!!





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS