Archived

This topic is now archived and is closed to further replies.

Strife

Linked list example?

Recommended Posts

Strife    374
Hey, does anyone know of an example that implements a linked list in a game, preferably with classes? I understand the basics of linked lists, but I''d kinda like to see some more in-depth examples than what I have seen, which basically consist of nodes that basically only show something like name and age or whatever. Any replies would be helpful. Excuse me whilst I conquer Earth... Commander M (a.k.a. Crazy Yank) http://commanderm.8m.com CmndrM@gdnmail.net

Share this post


Link to post
Share on other sites
ImmaGNUman    122
Linked lists are very important in games, mostly in the form of holding animations, and of course, BSP trees. Look up the quake source.

-----------------------------

A wise man once said "A person with half a clue is more dangerous than a person with or without one."

The Micro$haft BSOD T-Shirt

Share this post


Link to post
Share on other sites
ToddH    122
Hi,
Just define a node class, that holds your game object as it''s element. The Node should also hold a reference to the next (and possibly previous) Node in the list.
In this way, you can have arbitrary nodes storing objects, which you can resuse for different apps.
Then define a linked list class, that has the usual methods insert first/last etc.
If you want some code or something, mail me.. Todd.
Toddhau.yahoo.com.au

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
ImmaGNUman,
Actually BSP trees are usually implemented as binary trees, rather than linked lists
(Don''t you just hate picky people like me? )

Share this post


Link to post
Share on other sites
Gregor_Samsa    122
Hullo,

I was just wondering, is a link to the previous node required in a linked list? Wouldn''t it save a lot of memory to go without one? Also, is it more efficient to create a linked list object or just have functions, like in C?

P.S. - What is a BSP tree? I''ve heard of them, but I have no idea what they are.

Share this post


Link to post
Share on other sites
bishop_pass    109
quote:
Original post by Gregor_Samsa

I was just wondering, is a link to the previous node required in a linked list? Wouldn''t it save a lot of memory to go without one? Also, is it more efficient to create a linked list object or just have functions, like in C?

P.S. - What is a BSP tree? I''ve heard of them, but I have no idea what they are.



A link is required to the prior element if you want efficient deletion of random items. This way you can reference the prior item quickly and link it up the item after the item you just deleted.

As for BSP trees, a BSP tree is a tree that grows the delicious BSP fruit.





Share this post


Link to post
Share on other sites
NewDeal    134
A BSP tree is a way of performing hidden surface removal in 3D apps. Its basically a way of dividing the 3D space into sectors and only showing the ones visible to the player.

There''re lots of tutorials in the programming section here on GD.

Share this post


Link to post
Share on other sites
Holden    122
Hello.
I''ve got a great linked list class that is Template based.
the code is very simple and there is also a demo program.
I can give it to anyone, just ask for it from:
preshel@mailcity.com

I will send you the zip file.

Share this post


Link to post
Share on other sites
drago    150
quote:
Hello.
I've got a great linked list class that is Template based.
the code is very simple and there is also a demo program.
I can give it to anyone, just ask for it from:
preshel@mailcity.com


I prefer to use STL containers/iterators... It saves from re-inventing the wheel.. Although implementing one yourself is always a good excercise..

----------
Mail me, Drago's OpenGL Website

Edited by - drago on November 3, 2000 8:28:13 PM

Share this post


Link to post
Share on other sites
ToddH    122
Links to the prior element in a list are required if you want to add and remove from the head and tail of the list, at least efficiently. Remember that this is only really an issue if you have a large list. If you have lots of little lists, it is best to go with a singly linked list, where you don''t really need the overhead of the extra pointer.
(btw, BSP can be implemented by binary trees, which in turn must be implemented by an underlying ds, most likely a linked list).
Todd.

Share this post


Link to post
Share on other sites