PDA

View Full Version : Importance of Link Lists



Nick Sedich
05-14-2002, 05:31 AM
Hello, after reviewing some old stuff from the college level AP Computer Science cirriculum, I saw a strong emphasis on link lists. My question is, how important are link lists in OpenGL \ Game \ Graphics development. I know pointers are needed, but are link lists really just a crazy way of making sure the programmer has a solid understandment of pointers. http://www.opengl.org/discussion_boards/ubb/frown.gif

davepermen
05-14-2002, 05:38 AM
well, for opengl they are not important at all, as this question is not related to gl.
but as you asked yet
first:it helps a lot in understanding how the stuff works
second:for high dynamic changing amount of data, that has to be sorted, they are cool (possibly particles with z-sort in an explosion wich can generate subexplosions as well or something)
third:using stl, i can choose between arrays,vectors,lists etc and don't have to care how they work, just where they are good in http://www.opengl.org/discussion_boards/ubb/wink.gif

[edit] i always switch sdl and stl http://www.opengl.org/discussion_boards/ubb/wink.gif

[This message has been edited by davepermen (edited 05-14-2002).]

Nick Sedich
05-14-2002, 05:43 AM
Yeah, I kind of figured that link lists were not important, but do have some value. Like I said its really just a way of understanding pointers. Heh, I have to learn OpenGL after I'm done with this college level c++ work, I mean just about three quarters of it will be useful when I begin OpenGL development. http://www.opengl.org/discussion_boards/ubb/smile.gif

Humus
05-14-2002, 06:25 AM
IMO linked lists are one of the most useless data structures ever invented. Not only is it confusing, it's performance sux for many kinds of operations. A dynamic array is easier to implement (takes like 10 minutes at most), is faster and more flexible for almost all kinds of tasks.
The only real use for something like a linked list would be if one would implement something like a stack.

nickels
05-14-2002, 06:42 AM
There is always some need for a linked list. The main criterion are:

1) You don't have an upper limit on the number of items you are going to have to deal with (yes, the dynamic array can do this).

2) You need to insert and delete objects from the middle of the list (try doing this with your dynamic array, not).

Having a good que/stack class coded up is an essential tool for the programmer. In C++ you may as well use STL, but in C you're going to need to have your own floating around.

Knowing when to use a linked list as opposed to another structure is a matter of experience and judgement.

I often read input files into linked lists and then solidify them (i.e. copy them into an array) once I know many items I am dealing with.

There are a lot of programmers out there who never use linked lists (often because they don't have the brains to understand how they work). These are the guys whose code you have to crack open every year or so to bump up the max_index on their arrays so as to stop the core dumps.

A programmer who doesn't know how to use a linked list might as well be a java programmer as far as I am concerned. They obviously just got into programming because they heard there is money in it, not because of interest. Those people are destroying this profesion, makeing all of the competent programmers have to put up with a whole bunch of stupid process just to guard against their making mistakes and blowing million dollar projects.

Ha! How do you like those bananas?

[This message has been edited by nickels (edited 05-14-2002).]

[This message has been edited by nickels (edited 05-14-2002).]

Ysaneya
05-14-2002, 06:54 AM
Have to agree with Humus. I use linked lists in this case:

- the number of items to store is not too high (memory overhead);
- no need for direct access to the elements;
- generally, no need for speed.

That is, i don't think i'm using them once in my engine, though i might need them one day.

Y.

Nick Sedich
05-14-2002, 08:57 AM
I guess alot came out of this whole link list deal, even though its quite the contrary to the sites purpose. Its funny, why does my computer science teacher, and teachers in general bother going over link lists. I believe that the whole computer science cirriculum is corrupt. I seldom tell people that the knowledge they know is probably enough to begin OpenGL or at least begin working on some lead in's into game design and architecture. Ah... and not to mention I consider myself lucky that I had the oppurtunity to at least learn C++, because much to my dislike next year they are changing the whole cirriculum to Java, which sucks. John Carmack even said its not worth while. Ah, might as well drop out of college lol. http://www.opengl.org/discussion_boards/ubb/smile.gif

tod_baudais
05-14-2002, 09:06 AM
Linked lists are very important to understand as they form the basis for the many tree like structures you'll need later.

Tod

Tom Nuydens
05-14-2002, 09:48 AM
Originally posted by Nick Sedich:
Ah... and not to mention I consider myself lucky that I had the oppurtunity to at least learn C++, because much to my dislike next year they are changing the whole cirriculum to Java, which sucks. John Carmack even said its not worth while. Ah, might as well drop out of college lol. http://www.opengl.org/discussion_boards/ubb/smile.gif

I'd love to hear why you think Java sucks. "Because Saint John of Carmack said so" is not a valid answer. Neither is "it's slow". Java is a tool with many applications. 3D game programming just isn't necessarily one of those applications.

The same goes for the linked lists. Nickels already posted two very good reasons why linked lists can be useful. Just because you don't necessarily need them in your little 3D project, does not mean that they are useless.

Your attitude is all wrong -- stop being so unbelievably short-sighted. You can thank me later http://www.opengl.org/discussion_boards/ubb/smile.gif

-- Tom

rlskinner
05-14-2002, 10:02 AM
John Carmack may think Java sucks (for 3D game programming), but I'll bet he knows when a linked list is the appropriate tool for a job.

You know, I've got a funny little screwdriver-shaped tool called a "torx". I don't use it all the time. I don't even use it much at all. But I know how to recognize when its the right tool.

You should sit back and learn a bit about programming before you decide you know everything. Believe it or not, computer scientists haven't been spending the last 30 years learning, developing and *teaching* programming techniques just to torture you with linked lists.

Devulon
05-14-2002, 10:05 AM
I personally am not a big fan of java. But this is only because in the work I do it simply isn't useful (or adequate). I over the years I have become more accepting of java. For graphics its out. For low level programming of course its out.

As for linked lists they are very important and carmack will definately agree. If you don't understand linked lists you will definately have trouble with quad trees or bsp trees or any type of scene management. And let me tell you every version of quake (and even the new doom) use bsp's. Even the PVS is basically a linked list to other visible nodes. The entire engine is based on building an extremely complete and efficient and of course complex system of links. Without them quake wouldn't be possible.

Devulon

Humus
05-14-2002, 10:48 AM
Originally posted by nickels:
There is always some need for a linked list. The main criterion are:

1) You don't have an upper limit on the number of items you are going to have to deal with (yes, the dynamic array can do this).

2) You need to insert and delete objects from the middle of the list (try doing this with your dynamic array, not).


1 as you said is solved just as easy with a dynamic array.
2 can be a little problematic with a dynamic array, still I wouldn't recommend a linked list if this is the case. A binary tree is usually what's needed in this case, which btw often is a simplier concept and has higher performance. In many cases you're not really interested of order either, and in that case the need to insert an item in the middle of the list dissappers, and deleting a object from the middle of the list becomes a simple task, just replace it with the last element and shorten the list by one.


I should say though that linked lists can be a good for educational purposes, learn the concepts for pointers and such. But for more practical purposes there are almost always other more suitable data structures you should use instead.

Gorg
05-14-2002, 10:50 AM
About John Carmack and Java :

I don't have the actual .plan, but he never said that java sucked. What he said is that he thought about using it for the script language instead of writing his own VM, but due to compatibility problem with the Java VM in Linux, he could not use it. That's all he said.

Today, you could use it, as Sun releases the VM for all platforms. The only incompatibilities you can encounter are in the GUI.

But since Id games need to be ported to consoles(XBox will never have java!), then Java is still not option for them.

Gorg
05-14-2002, 11:25 AM
Originally posted by Humus:
1 as you said is solved just as easy with a dynamic array.


Well it might not solve it as elegantly. It really depends on the number of objects and the resize policy of the dynamic array. The most common policy in the STL is to double the memory needed on resize.

Well, if you store for 2 megabytes of objects in your dynamic array and you get a resize at that point, you will have 2 more megabytes allocated there and unused and worst you have a copy of 2 megabytes.

You can argue that 2 megabytes is nothing for todays or that usually the only thing that are stored in the containers are pointers are handles which are very small(let's say 8 bytes) and so to get 2 megabytes, you would need about ~125000 objects which is not realistic(I think, I might be wrong, I am not writing games) in today's game. And I would say you are right.

But for other software it might not be so ridiculous. I am working on a non real-time(but time constrained nontheless) application and the maximum object I got so far was ~50000. So when I insert the 50001st object, I don't really want to have the whole 450 kbytes of data copied. There are enough slow modules in the software already.

So I prefer the scalability of the list. But as always it all comes to "know your problem and use the right tools to solve it".

Nick Sedich
05-14-2002, 12:27 PM
Yeah your all absolutely right about the whole principle behind "Right Timming" and knowing when to implement particular programming principles at certain times. However, we all know there is a fine line between product developing and getting something done, and fudging around with a few pointers. Like some of the other people commented link lists really dont hurt your application, but then again why do you think Computer Science scientist and mathematicians spent time developing matrices and arrays? Internally the compiler is just translating your matrices and arrays into link list type data structures and maintains it automatically for you. I mean, I'll tell you, and it doesn't take fool, but computer programmers like myself are evolving into a era where computer resources are highly abundant and just about anyone can pop in 256 megabytes more ram, thus sufficing the whole "optimization" process. Needless to say, Link Lists are great, and so are binary tree's. If anyone has the time, can you explain why I'm being taught how to do "graphing" involving Binary Tree's, and making all the nodes in the tree accesible to any other Node? Wouldn't that be just a array in simple words http://www.opengl.org/discussion_boards/ubb/smile.gif

davepermen
05-14-2002, 12:32 PM
you know what?
anyone asking why someting should be useful is not adult enough to just see how useful it is to know something. i was in school now for 12 years and all i learned is, what i did not learned i needed sometimes, what i learned, i could use sometimes. its all useful.

or how my math - teacher told us all:
all you need is to _SEE_ the stuff..

once you've seen how something works, you don't have to know it anymore, you just can it..

once you see datamanagement,pointers,lists,linking and its use, you never ask again..

try to dive into databases, its a funny topic, and you'll learn a lot for games..

knowledge is our weapon.

oh, and some other thing to learn..
this is not a forum about programming structures and how useful they are.. its about opengl. and for opengl, linked lists of your data don't have any use, as gl can't parse your lists.

jwatte
05-14-2002, 02:03 PM
Vectors suffer from reallocation penalty and/or block overhead penalty, AND they can be a pain in the ass in situations where contiguity cannot be guaranteed. Not to mention that they will cause lots of unnecessary copy construction for non-binary objects; thus there's many cases where a linked list is the right choice.

As far as I'm concerned, there are four containers, and you have to know which of the four to choose for each task:

1) Vector
2) Linked list (ideally double)
3) Hash table (with chaining)
4) Sorted tree (AVL, R/B, B-, ...)

Anyway, until you've gone through a decent algorithms class, and until you've actually run profiles on a few real, live, working systems, I don't think you should be marrying yourself to any particular container, because you probably haven't seen most cases where each container is a good fit yet.

Humus
05-15-2002, 11:21 AM
Originally posted by Gorg:
Well it might not solve it as elegantly. It really depends on the number of objects and the resize policy of the dynamic array. The most common policy in the STL is to double the memory needed on resize.

Well, if you store for 2 megabytes of objects in your dynamic array and you get a resize at that point, you will have 2 more megabytes allocated there and unused and worst you have a copy of 2 megabytes.

You can argue that 2 megabytes is nothing for todays or that usually the only thing that are stored in the containers are pointers are handles which are very small(let's say 8 bytes) and so to get 2 megabytes, you would need about ~125000 objects which is not realistic(I think, I might be wrong, I am not writing games) in today's game. And I would say you are right.

But for other software it might not be so ridiculous. I am working on a non real-time(but time constrained nontheless) application and the maximum object I got so far was ~50000. So when I insert the 50001st object, I don't really want to have the whole 450 kbytes of data copied. There are enough slow modules in the software already.

So I prefer the scalability of the list. But as always it all comes to "know your problem and use the right tools to solve it".



Sure, there is a possibility of unnecesary memory allocation. Nothing says you need to use 2x, you can use 1.5x if you want too, depends on what's more important, less memory or less copying. Also, in situations where you are just filling it up but come to a point where you know you wont need to add another element (say you just loaded a file and put the elements into the list) then you can add another function that just resizes the allocation to free any additional memory that may not be needed.

Regarding memory overhead, a dynamic array only contain a small amount of data beyond the actual array content, probably less than 32bytes. A linked list will need to have an extra pointer in each node, or even two if it's double linked. If the elements are small this can have a serious impact on memory usage. If you're storing plain integers you'll have 3 times are much memory allocated than what you need in case of a double linked list. Not to talk about malloc/new overhead, especially if constantly adding and removing lots of small memory areas it may easily cause serious memory fragmentation. I think in many applications this easily overshadows the copying that may occure with dynamic array. It's evenly distributed though with linked lists.

ffish
05-15-2002, 06:26 PM
Originally posted by Nick Sedich:
Yeah your all absolutely right about the whole principle behind "Right Timming" and knowing when to implement particular programming principles at certain times. However, we all know there is a fine line between product developing and getting something done, and fudging around with a few pointers. Like some of the other people commented link lists really dont hurt your application, but then again why do you think Computer Science scientist and mathematicians spent time developing matrices and arrays? Internally the compiler is just translating your matrices and arrays into link list type data structures and maintains it automatically for you. I mean, I'll tell you, and it doesn't take fool, but computer programmers like myself are evolving into a era where computer resources are highly abundant and just about anyone can pop in 256 megabytes more ram, thus sufficing the whole "optimization" process. Needless to say, Link Lists are great, and so are binary tree's. If anyone has the time, can you explain why I'm being taught how to do "graphing" involving Binary Tree's, and making all the nodes in the tree accesible to any other Node? Wouldn't that be just a array in simple words http://www.opengl.org/discussion_boards/ubb/smile.gif
Link lists have a place, just like arrays. I suggest you read a good text like Cormen et al's "Introduction to Algorithms" to find out why/where each should be applied. Link lists can hurt your application when used incorrectly, as can arrays.

Internally your compiler is not translating arrays into link list-type data structures and maintaining it automatically. I suggest you read some good C texts or even better, some x86 assembly language texts. You will find an array is basically a contiguous block of memory. No pointers to next elements are kept, apart from the invariant that memory addresses are contiguous.

Computer resources might be highly abundant, but 256GB of RAM won't help if you're using e.g. bubble sort where you should be using quicksort or radix sort. That is, computer resources won't help the whole "optimization" process at all without the correct data structures/algorithms.

"Graphing" using Binary Trees? Firstly, if you didn't know, graphing in this context has nothing to do with computer graphics. Secondly, binary trees are not used to represent graphs, although they may be a special case of a graph. A graph is most certainly not just an array. I would guess that you are learning about graphs because they have many applications, like representing network topologies, as well as being used to demonstrate many classic CS problems like the Travelling Salesman.

I apologize if you are genuine, but your post sounds like a troll. If you are genuine, please read a good algorithms book, and learning a bit about computer architecture can't hurt either. Preferably do both before trying to learn OpenGL as it will ease the process.

Hope that helps.

IT
05-16-2002, 06:00 AM
I can't believe we're discussing something as fundamental and simple as linked-lists.

Linked lists are/can be used for trees, stacks, queues, open hash tables, or whatever.

This is CS 101. Linked lists are used all over the place.

deshfrudu
05-16-2002, 06:57 PM
Extra credit. Doubly-linked lists (that is, each node points forward and backward) with only one pointer per node. How?

nutball
05-16-2002, 10:16 PM
Originally posted by deshfrudu:
Extra credit. Doubly-linked lists (that is, each node points forward and backward) with only one pointer per node. How?

How many links to have want to traverse to reach the previous node? Otherwise a simple circular linked list will do ya.

tfpsly
05-16-2002, 10:36 PM
1) Every1 should know how linked list works, that's such a basic storage tool

2) Linked list are very usefull when you are storing "objects" without knowing their quantities, AND when you have to access them sequentially AND when you do not need to perform seek operation (no search in the list, or at least no search in the main loop of the program).

They can even be quite usefull in a 3D engine. For example to store lists of objects to be rendered, lists of animation tracks of each object...

Robbo
05-17-2002, 02:12 AM
Having read all of the above, I have to tell a short story - I have seen a couple of 3d engines (or should I say `demos') that actually join vertices together into linked lists (yup, with pointer_to_next etc.). The linking information being almost as large as the vertex itself.

Now call me old fashioned, but this is probably the dumbest use of a linked list I could ever imagine.

Nick Sedich
05-17-2002, 01:02 PM
Heh, thats funny, better of dumping them into a matrix, or maybe some diagraphs. :

Lev
05-17-2002, 04:49 PM
This thread seems not to end, so I'll add my opinion:

whenever you need random access linked lists suck big way. And the great majority of all problems that need lists(esp. in graphics) need random access, and therefore can be solved better with regular arrays.

-Lev

[This message has been edited by Lev (edited 05-17-2002).]

ffish
05-18-2002, 06:00 PM
Originally posted by Nick Sedich:
Heh, thats funny, better of dumping them into a matrix, or maybe some diagraphs. :

Diagraph? I'll assume you mean digraph. Why would you use a matrix, and why would you use a digraph. It is possible that you would use a matrix for holding vertices (although I've never heard of it being done before and I can't think of a good reason to) but digraphs would be much worse than linked lists. Best representation for vertices is an array. Read up on plain vertex arrays, CVA's and VAR.

For the second time, you sound like a troll. If not, please read a data structures/algorithms text before making comments that you obviously don't understand.

Maybe you could try http://www.nist.gov/dads/