PDA

View Full Version : Linked Lists & TList



Gadget
15-01-2004, 01:50 PM
I have been told on here in the past to use Linked Lists to keep track of objects and creatures in my MMORPG. I proceeded to use a 2 dimensional array of TLists. ie.

400 x 400 x TList. Where TList can contain several items on one tile location.

I just read this on gamedev:-

http://www.gamedev.net/reference/articles/article2041.asp

The question is, is a TList the same thing? If not, do I have to implement a TLinkList myself? Which is fastest? I am using Delphi 4 btw.

Alimonster
15-01-2004, 02:41 PM
I don't think that TList is an actual linked list, although it is a damned useful class.

AFAICT, a TList is actually a "vector" (in C++)-like structure. In other words, the list itself is stored with dynamically allocated memory, which will be contiguous (array-like). When adding elements, the capacity is checked. If there's not enough memory in the TList then the memory block is increased in size, by an amount that depends on the amount of memory already allocated. So, it's like a dynamic array that automatically ensures it has enough elements (no calls to SetLength), if I'm interpreting the VCL source code correctly.

The advantage here is that a TList uses contiguous memory, which means fast random access (think random access = speed of array, basically). The down side is that reallocation when the capacity is reached could become a bit costly (since data may need to be shuffled to another spot if the current memory block can't fit -- i.e., reallocate and copy the memory to a bigger place).

Now, an actual linked list will behave differently. Linked lists can't really guess how many elements will be added, so they'd allocate one node per element-to-be-added. Each node will be allocated to a different place in memory, since they're separate allocations, and pointers are used to link the nodes together.

Linked lists won't be as quick for random access as TList because the nodes are not contiguous in memory - they're all over the place, and the only way to know where is to follow the trail of pointers. Linked lists prefer sequential access (iterating over the nodes from start to finish in that order, or the reverse depending on whether you have a singly-linked list or a doubly-linked list).

The most significant differences between the two would be in access patterns and the time taken for insertions/deletions. You do NOT want to access proper linked lists in a random access fashion, like you would do unthinkingly for arrays. :shock: The only way to go from one list element to the next is by following the trail of pointers. This could have innocent or disastrous consequences, depending on how the linked list is structured. Consider the following, if a hypothetical list provides a default operator for array-like access to elements:

var
i: Integer;
begin
for i := 0 to MyLinkedList.Count - 1 do
MyLinkedList[i].Blah(42);
end;
The above looks innocent until you consider this... The first time around, you're saying "get list element 0". This can be grabbed initially without any looping, since we have a head pointer pointing right at it. Next, you'd get element 1 -- so it starts at 0, goes to 1, and uses that value. The next time around, it's 0,1, then 2. Then 0,1,2, and 3. Next 0,1,2,3, then 4 (and so on). Your only hope here is that the author has decided to include some sort of "current" pointer to the last returned element to save you from yourself -- but keeping this in synch can slow down other operations.

Linked lists demand a different access strategy. Perhaps something like this:

var
Current: PListElement;
begin
Current := MyLinkedList.GetFirstNode;
while Current <> nil do
begin
Current.Blah(42);
Current := Current.Next; // or maybe request it from the list
end;
end;
The difference should be obvious -- you're only ever considering the current node, doing stuff with it, and going on to the next one.

You might prefer to avoid exposing the list nodes of a linked list (maybe include callback functions or use the Visitor design pattern) as it's preferable to avoid exposing class internals in such a blatant way, but that's a personal choice.

I've not checked how TList handles insertions and deletions, but think about it -- if adding to the middle of an array, you have to shuffle all elements to the right of that position one element further to make room, then put the new one in the vacated slot. This shuffling of memory could be costly as the amount of elements increases. However, adding and deleting from linked lists is a trivial swapping of pointers and will always be quick (except perhaps for actually _getting to_ the element by sequential access, but I'm assuming here that you'd have it sitting around to be deleted).

You can only move one way through a standard linked list, as each node will only have a "next" pointer. However, you can (and I usually do) have "doubly-linked lists", which include a next and previous pointer. I find that these are much handier at the cost of only slightly more fiddly code (but not enough to worry about). I always include a tail pointer as well as a head pointer.

Now, you do not have to implement your own linked list if you choose to do so. Nope, you don't, because I have a class sitting around for you to use. ;) This depends on you deciding to use actual linked lists rather than TLists, of course, which is a choice you must weigh up yourself.

I'll post another message tonight about the list class once it's tidied.

Feel free to ask if you want more info about linked lists.

Harry Hunt
15-01-2004, 07:17 PM
I remember that in an older version of Delphi (I think it was 2.0), TList was difined like this:
type TList = array [0..MAX_INTEGER] of Pointer;
I don't think it works like this anymore though.

Another alternative: Dynamic arrays. You can create dynamic arrays of variant records to store different kinds of information.
From what I've read, dynamic arrays allocate larger "chunks" of memory and allocate additional "chunks" of memory as soon as you go past the size of one of those chunks. Now I'm not sure about this, but if that is actually how they work, they're probably faster than linked lists or TLists (at the cost of memory).

I might be totally wrong here, just repeating some stuff I read and heard somewhere.

Gadget
16-01-2004, 03:28 PM
Thanks for those replies ;)

Wouldn't mind seeing a sample class that I could use and modify!

Alimonster
16-01-2004, 03:48 PM
It'll probably be Sunday evening before I can give you the unit - my life is totally busy at the moment!

Harry: I think your comment about "TList = array [0..MAX_INTEGER] of Pointer;" may be about a slightly different part of the class. I believe you're thinking of the internal declaration of a TList's buffer, rather than the class itself. The class has a type like the above (I forget its exact name) as a way to avoid range check errors - there's also a pointer to it. In essence, the code is saying "The internal buffer size could be anywhere up to {ridiculous size} in length", so that when it's accessed via a pointer there ain't range check errors. The pointer itself is just dynamically allocated + reallocated as required (remember that dynamic arrays weren't available until Delphi 4 and TList predates that) to get the correct amount of elements.

Harry Hunt
16-01-2004, 10:27 PM
Cool, thanks for clearing that up for me.

Alimonster
21-01-2004, 03:25 PM
I did a private message giving Gadget my linked list unit and instructions on using it. I still fancy adding a bit more functionality to it before posting a link here, though. In the meantime, I'll point people in the direction of other Delphi container classes.

Julian Bucknall (author of "Tomes of Delphi") has some container classes here:
http://www.boyet.com/FixedArticles/EZDSL.html

Also, there's a project at SourceForge called Decal:
http://sourceforge.net/projects/decal/

Gadget
28-01-2004, 06:11 PM
I did a private message giving Gadget my ]http://www.boyet.com/FixedArticles/EZDSL.html[/url]

Also, there's a project at SourceForge called Decal:
http://sourceforge.net/projects/decal/

Thanks for all your help :) Managed to implement Linked Lists, but to be honest I found that TList is also comparably fast. Of course, there are advantages to using linked list as it's easier and faster to insert things.