Linked Lists

[xGTx]

Anyone know of or have any tutorials on linked lists, and what can you tell me about them? Benefits, where used... why not to use them.. why to use them... how they work logically.. thanks! i've been wanting to learn about these. thanks!

[Nightmare_82]

There are two types of linked list:
Single linked list
It works like this:
You need a class which has a pointer to the first and to the last element. Each Element added has a pointer to the next element. If there is no next element the pointer is nil.
When to use it:
Use linked lists, when you often need to add items to the list. Adding is very simple. You only have to set the neighbour of the last element to the new element. Deleting an element is a little bit harder:
You have to set the neighbour from the previous to the following element. To find out the previous item, you have to search for the item which has the current item as neighbour. That works better with:
Double linked list
In a double linked list, each element has a pointer to the previous and the next item. When you delete an item, you do the following:
Previous Item: set next item to the right(the next item of the current) item
Next item: set previous item to the left(the previous item of the current) item.
You don?¢_Tt need to search for the previous item, because the information of both neighbours is stored in the current item.

So, it's better to use lists instead of dynamic arrays when you often have to add or delete items. When you often delete items, a double linked list is faster. Otherwise, use a single linked list. When you want to move through the list, you need to add methods like First, Next and for Doble Linked List Previous.
When you need to acces the elements per index, a list is bad, because it has to search from the beginning to the index.

Sorry for my bad English. I hope I could help you.

[xGTx]

Could i see perhaps an example to help clarify what you just said?

[Nightmare_82]

http://www.ibrtses.com/delphi/dllist.html here is an example of a double linked list.

[xGTx]

I still hardly understand what they are good for...

Can't you just use a TCollection or something?

[Harry Hunt]

Bevor dynamic arrays existed, linked lists where one of the very few ways of creating lists with a variable length. Today, there are other ways of achieving that, but linked lists are still quite useful and they can be very fast for certain operations.

Linked lists come in all kinds of "flavors". A stack is a linked list, a queue is a linked list, etc.

I rarely use linked lists if all I need a dynamic array because in most cases, it won't give you any performance advantages. For stacks however, linked lists are perfect and they will outperform any array or collection.

[xGTx]

[quote="Harry Hunt"]
I rarely use ]

What do you use then?

My problem is: Holding a list of tiles with another list that holds wich texture ID those each individual tiles are on.

Sort of like (an an abstract view):

Anim_Tiles: 23,64,45,45,76,45
Anim_Text: 01,02,01,01,02,01

That way my engine can see that the 1st tile in the animation is 23, and that tile is on texture 01. So on and so fourth. My idea right now is using 2 TStringLists If you think you have a fast way of doing this, im all ears. Thanks alot.

[Harry Hunt]

don't use string lists. you're using numeric data and string lists hold strings (duh!) which is more than you need.

You could either use two dynamic arrays of Byte (or whichever range you need) or you could do something like


type
TFrame = record
TileId: Byte;
TextureId: Byte;
end;

var
MyArray: array of TFrame;


or you could use a TList (see Delphi help file).

If you don't need an "Insert" function, I'd use a dynamic array of TFrame...

[xGTx]

Now adding to a dynamic array is simply:


TAnimationFrame = record
TileIndex : Byte;
TextureIndex : Byte;
end;


Frames : Array of TAnimationFrame;


SetLength(mTile[X, Y].Animation.Frames, High(mTile[X, Y].Animation.Frames)+2);

Right? I think i may be wrong here, please correct me.

[Harry Hunt]

yep, exactly

[xGTx]

Is it always like

SetLength(mTile[X, Y].Animation.Frames, High(mTile[X, Y].Animation.Frames)+2);

or does it depend on the sizeof(frames) ?

[Harry Hunt]

Don't use SizeOf in this context, use Length. SizeOf will return the Byte-Size of the pointer which is always 4 bytes. Length will return the number of elements in a dynamic array. To append an element to a dynamic array, do this:

SetLength(Frames, Length(Frames) + 1);
Frame[Length(Frames) - 1].Color := clGreen;

[xGTx]

Doesn't High() do it?

[Harry Hunt]

yeah, high() will do it, too

[xGTx]

Whats the difference between the output of High() and Length() ?

And this is acting very strange: (giving me range check error after like 3 iterations of this functions)

SetLength(mTile[X, Y].Animation.Frames, Length(mTile[X, Y].Animation.Frames)+1);
mTile[X, Y].Animation.Frames[Length(mTile[X, Y].Animation.Frames)-1].TileIndex := frmMain.cTileID - (Trunc(frmMain.cTileID div 112) * 112);
mTile[X, Y].Animation.Frames[Length(mTile[X, Y].Animation.Frames)-1].TextureIndex := Trunc(frmMain.cTileID div 112);

[Useless Hacker]

Whats the difference between the output of High() and Length() ?Length() returns the number of elements in an array (or the length of a string); High() returns the index of the last element in an array - usually this is Length()-1. There is also the Low() function, which returns the index of the first element in an array, and will in nearly every case be 0. It is, however, possible in Delphi to have static arrays that do not start at index 0, for example if you are using an enum as the index.

[cairnswm]

I think Dynamic arrays always start at 0.

[WILL]

I think Dynamic arrays always start at 0.
Thats exactly right, they always start at 0. When you
var dArray : Array of Char;
SetLength(dArray, 20);
dArray will be from 0 to 19. Then
a := Length(dArray);
// a = 20

b := High(dArray);
// b = 19

c := Low(dArray);
// c = 0

Just be careful how you use Dynamic arrays within other data structures. The effects can be a bit unpredictable. Misuse of them is what would result in a 'memory leak' in your program. Dynamic Arrays within dynamic arrays is also highly UNrecommended(if your program will even function properly). You re pretty much dealing with memory management when you play with them.

[xGTx]

Thanks alot guys. Now removing from a dynamic array is



SetLength(Frames, High(Frames)-1);


Since high() is the actuall number of elements in the array and -1 would drop it down 1. Correct?

[Harry Hunt]

No, High is the last index of the array and Length is the count.
To delete the last item do this

SetLength(MyArray, Length(MyArray) - 1);

or this

SetLength(MyArray, High(MyArray));

[xGTx]

Yeah, thats what i meant im sorry. I've got my dynamic array working fairly fast for my animations. Thanks for the help and clarifications

[cairnswm]

Not relevant any more but

http://www.awitness.org/delphi_pascal_tutorial/source/LIFO_stack_linked_list.html

has an example on creating linked lists the good old fashioned way :)

[Paulius]

From you?¢_~re adding and removing question?¢_Ts it looks like you?¢_Tve got an incorrect view of how setlength works. It makes no sense to increment or decrement dynamic array size be one, because when resizing the array what happens is a new chunk of memory is allocated, then the old values get copied and the old array gets destroyed. It?¢_Ts a much better idea to keep a counter of how many items you have in the array, and if it?¢_Ts full make it larger by some (certainly bigger than one) value. When removing items from the array the fastest way if you do not care about item order is to copy the last item over the item you?¢_Tre deleting and decrement the item counter, but if you care about item order and don?¢_Tt have a lot of items a linked list will be faster.

[cairnswm]

If you are storing instances of a class in the Array you are effectivly only storing a pointer anyway. (So size allocation isn;t too relevant) but it is a good point that decreasing the array is going to be slow and it is more efficient to store the whole array all the time.