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

[pascal]
type
TFrame = record
TileId: Byte;
TextureId: Byte;
end;

var
MyArray: array of TFrame;
[/pascal]

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:

[pascal]
TAnimationFrame = record
TileIndex : Byte;
TextureIndex : Byte;
end;


Frames : Array of TAnimationFrame;


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

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

[Harry Hunt]

yep, exactly