RE: Linked lists

[Kamel Serend <kserend@twowaytv.co.uk>]

Hy,
To make thing simple, imagine you're one Node. You would like to know the
address of you next neighbour. For that, you ask your agenda called NEXT and
then you follow the instruction and find your neighbour. And so on.
A second thing that would be nice to have is another agenda that could give,
for your neighbour, your address. Let's call it PREVIOUS. For the first
neighbour, there would be no PREVIOUS agenda, nor would there be a NEXT
agenda for the last neighbour.
Everytime a new neighbour comes in the street, there's a huge party where
the last neighbour updates his NEXT agenda by putting the address of the new
fellow neighbour and the latter does the same by saving the address of the
last neighbour in his/her PREVIOUS agenda and by setting nothing to his/her
NEXT agenda. Then the new neighbour becomes the last one by specifying in
the BIG AGENDA of the street that the last to come is the new neighbour.
This approach can also be applied to people living in many different streets
around the town, but whatever the place, the street is always coded
according to the same structure, so it does not really matter : once we have
an address, we can find the guy.

Now, let's draw the parallel with the dynamic linked list.

	struct nodeType
	{
		int NeighbourInfos;
		NodeType * PREVIOUS;
		NodeType * NEXT;
	};

	struct nodeList
	{
		NodeType * HEAD;
		NodeType * TAIL;
		int NodeNumber;
	};

	Now, when you create a new list, you have to set HEAD and TAIL to
null: we haven't got any person yet. A desert street.
	When you start adding elements in the list, you have to link the
TAIL of the list to the new node, and set the NEXT parameter of the new node
to NULL so that we can wait for a new node. If the HEAD  is still NULL,
that's because the list is empty. Then, we have to set it to the first added
node. Finally, we can increment the number of node the list contains.
	When you add another node to a list that is already build, set the
PREVIOUS parameter of the new node to the tail of the list and set the tail
of the list to the new node and the NEXT parameter of the new node to NULL.
And so on...
	For the all-around-the-town side, this is to highlight the interest
of this dynamic list: the nodes are not sitting in a continuous portion of
the memory. Each node can be anywhere in memory and thus to allocate the
needed space is less tricky for the system and you are not limited to a
harcoded list. Your list can grow and be limited to 1000 elements like in
the first version.

	I hope this will help you to understand the code. I guess the main
idea to remember is "I have a new neighbour. I visit him. What must I do to
remember where he/she lives ?" And try to repeat the same process for the
new neighbour.

	Kamel.

	PS: I presented a double-linked list. In a simple one, you do not
pay attention to the PREVIOUS parameter, and thus have less worries to think
about.


> -----Original Message-----
> From:	John Oxley [SMTP:oxo42@yahoo.com]
> Sent:	Tuesday, January 01, 1980 10:24 PM
> To:	gameprogrammer@gameprogrammer.com
> Subject:	Linked lists
> 
> I am at the beginning of my last year in A-Level computer science, and
> this
> week, we have been covering linked lists. Our teacher gave us some C++
> code
> for 2 different types of linked lists, the first is easy:
> 
> struct nodeType
> {
> 	int component;
> 	int link;
> };
> 
> nodeType list[1000];
> int head;
> 
> obviously this is not dynamic. He also gave us a dynamic linked list,
> which
> I do not understand. I was hoping that someone could explain it to me.
> This
> is what he gave:
> 
=================================================================
The GameProgrammer.Com mailing list is for the open discussion
of any topic related to the art, science, and business of
programming games. This list is especially tolerant of beginners.
We were all beginners once

To SUBSCRIBE or UNSUBSCRIBE please visit:
http://gameprogrammer.com/mailinglist.html