Extra credit. Doubly-linked lists (that is, each node points forward and backward) with only one pointer per node. How?
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.
-
Every1 should know how linked list works, that’s such a basic storage tool
-
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…
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.
Heh, thats funny, better of dumping them into a matrix, or maybe some diagraphs. :
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).]
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/