Linked lists, v2
Displaying 1-11 of 11 total.
1
Please enter a numerical value for the importance of this sticky.
Enter 0 to unsticky.
Feyr

gannon requested variable-length data fields for the linked list module I wrote yesterday, so I've uploaded Linked List Library v2. New features:

*Variable length nodes, with examples of how to use them
*ListReverse() function, which will reverse a list in O(N) time
*ListSplice() function, which will cut a chunk out of a list and splice it into another list, or the same list at a different location. (See the docs for caveats...the main one is that you can't splice a range into itself without breaking your list.)
*Various functions tweaked and added to support variable length nodes.

ListSplice() can also be used to move individual elements around, though you might want to write a wrapper function for it to make it a little less awkward if that's what you're using it for.

If you only wanted to store a single integer in each node (or four bytes, or two words) then you're better off sticking with version 1...the interface is a bit clearer.

*cough* Incidentally, when you're writing list code that deals with more than one list, be sure not to name them 'mylist' and 'mylist2'. I just spent half an hour trying to figure out why ListSplice() didn't work when you tried to splice from one list into another. Turns out I had mistyped 'mylist2' as 'mylist' in two different places. -_-

Posted on 2004-10-03 01:26:16

gannon

thanks this will be very helpfull :)

Posted on 2004-10-03 01:56:06

Technetium

I guess I should ask what these list things are... I looked at the list.vc code, and at the llists.txt that came with the zip, but I don't really get it. It looks like arrays, but other than the way they wrap around (which is cool, don't get me wrong), what is the difference?

Posted on 2004-10-03 02:29:04

Gayo

It's dynamic.

Posted on 2004-10-03 02:37:46

Kildorf

Linked lists basically are like arrays, but they have different ways of doing things that make them better for certain jobs.

An array works by setting aside a big block of 'nodes' (places to store data). You keep track of where the first one is, then add the index of the one you want (so, array[5] is array[0] + 5 nodes). It's quick to get to each node (you just have to add index*node_size to your beginning memory location) but woe unto you if you want to delete things and keep it neat, or to grow the array larger than you first declared it.

A linked list, on the other hand, doesn't have any particular size. You keep track of the first node (and possibly the last, depending on the kind of list). Then, each node has a link to the next one in the list. To get to a particular node, you've got to start at the first and hop over each one, because in your computer's memory they could be stored all over the place. However! If you want to delete a node, it's a simple matter of redirecting some links between nodes, and then cleaning up. And your list can grow to, basically, the size of your memory.

Oh, and lists have somewhat more overhead because each node has to keep pointers to its neighbours and whatnot.


When do you want to use which? Well... arrays are much better for Random Access -- if you're hopping all over the place, or just pulling data from random places. A good example would be, say, an item library where you're constantly pulling up stats for different items, but generally only one item at a time and in no particular order.

Linked lists, on the other hand, are much better for lists of items that will have to all be iterated over anyhow, and you don't know how many there'll be. A good example is, say, a list of monsters currently on the map. You'll have to check all of their AIs each tick (iterating through them) and you might have to delete and add quite a bit as you go, as they get killed or spawned.


Hope that clears something up. If I really botched up the explanation, please, someone correct me. :)

Posted on 2004-10-03 02:43:26 (last edited on 2004-10-03 02:44:13)

Feyr

That's a good question. I forget we're not all computer science students here.

Okay, a linked list is like an array, but it's one that grows and shrinks depending on how much data is in it. And it does so very quickly, unlike dynamic arrays, which often need to do a lot of copying if you try to insert or delete data from the middle or the front.

There are two (well, maybe three) main reasons why you might choose a linked list over an array. The first is that you need to do a lot of insertions and deletions from your array of data. A good example of this would be a windowing system. You'd want to be able to create new windows, delete old windows when they're closed, and reorder the windows (possibly by removing a window and reinserting it at the front of the list) when someone clicks on a window that's in the background.

The second is that you don't know exactly how much data you're going to be dealing with. For example, if your game allows the player to be followed around by the ghosts of people he's killed, you'd have to make an array big enough to hold the largest number of ghosts you'll ever need, with the risk overflowing the array and crashing the game if you make it too small, and wasting a lot of memory unless the majority of the array is filled.

The third is that you want to process data in either first-come-first-serve or last-in-first-out order. For example, you might want to print out a list of messages with intervals of a few seconds in between each message. You might not know when messages will arrive, either...perhaps the messages are status reports from a real-time battle system, and you need to give the player time to read one before replacing it with the next. With a list, you could add messages to the tail of the list and have a HookTimer or HookRetrace remove the any messages at the head of the list (in effect making it a queue) every few seconds and print them out. As long as the list is empty, nothing will happen. But as soon as you put one or more messages into it, they will slowly be printed out one by one until the list is empty again.

If you want a last-in-first-out order (which is what you get with a data structure called a 'stack') then you can get that by always adding/removing from the head of the list.

Here's a page with...uh...well, it looks basically like what I just said. But maybe you'll find this easier to follow: About linked lists

*edit*
Oh, this one is even better:
Using linked lists in games

Posted on 2004-10-03 03:01:43 (last edited on 2004-10-03 03:07:02)

Technetium

That sounds very useful. I'm not sure if I'll use it, just because it sounds a little over my head, but there are definitely places in my games where it would be useful, if I can get my brain to think in the right way. I'm probably the most inefficient VC coder in the Verge community, heheh, so I dunno how well it would work with my way of thinking out the code. ;-)

Posted on 2004-10-03 14:36:14

Tatzen

also arrays dont have nodes. they have elements. nodes imply linkage, but there isn't any.

Posted on 2004-10-03 16:56:44

Kildorf

That is true, but I was trying to provide a parallel so I fudged a bit there.

I am bad. ._.

Posted on 2004-10-03 17:10:57

Feyr


I'm not sure if I'll use it, just because it sounds a little over my head, but there are definitely places in my games where it would be useful


If you run into any places you'd like to use it but can't figure out how, feel free to ask for help. I tend to be a bit long-winded, but if you can stand that then I can probably give you some tips and suggestions to get you started.

Posted on 2004-10-03 18:23:44

locke

Linked Lists are great for item inventory systems, amongst many other uses.

-l

Posted on 2004-10-05 13:14:44 (last edited on 2004-10-05 13:14:45)


Displaying 1-11 of 11 total.
1
 
Newest messages

Ben McGraw's lovingly crafted this website from scratch for years.
It's a lot prettier this go around because of Jon Wofford.
Verge-rpg.com is a member of the lunarnet irc network, and would like to take this opportunity to remind you that regardless how babies taste, it is wrong to eat them.