Linked List Explanation

First of all, pointers (used in a Linked List) are just another way of representing data. Therefore pointers are again data structures. The difference this time, is that no programming language sets the data structure itself (like arrays). We cannot declare a variable like var data:pointer;.

Instead we need to create that type ourselves. We usually declare that type as a record. The reason for that is that we need to keep at least two pieces of information in our pointer. It should contain the value of what we want to save (it can be a string, integer etc..), but also the value of what it points too (usually another pointer or nil). 

So the first thing we do is we create a type which we will be using as a pointer.

So the declaration type TPtrNode = ^TListNode; shows we are declaring a type ourselves. The type we created is called TPtrNode so we can now make a declaration var pointer:TPtrNode;. Now that type is declared as ^TListNode. That means its a pointer to TListNode. What is TListNode? It's a record we will be declaring right now. As we said previously, our pointer needs to contain at least two pieces of information. 

So now, our variable pointer is of a type that points to this record. Therefore its a pointer. Note that one value of the record is of the type our variable is. That is done because a pointer points to another pointer. Therefore next is a pointer to another pointer. The element saved in every point is that of a string. 

If you have hopefully grasped what has been stated above we can now move even further into how pointers work. Instead of calling our pointer pointer it is conventional to call the first pointer in a linked list a head. Therefore var head:TPtrNode;. Note, to initialize a pointer we call new(head); (head is an example) to create a space in meomory for it. Say we want to add information to head we have to access the record it is pointing to. Since head is not a record itself but a pointer to a record, we cannot use head.element:='test';. Instead we have to use head^.element:='test';. One more information is needed in our record now. We need to fill the value next in our record pointed to by head. That now has to be a variable of type TPtrNode (like head since both are pointers). Also by convention, we usually use a temporary variable and put our information and make it next of an item in the list. So var temp:TPtrNode;. We now set its values like head, temp^.element:='test2'; temp^.next:=nil. Nil indicates the end of the list so it doesn't point to another pointer and that's ok. Even though next is of type TPtrNode we can also assign Nil to it indicating that we have nothing after that pointer. So now if we make head point to temp by doing, head^.next:=temp;, we have two items in our linked list. Head -> ('test') -> Temp -> ('test2') -> Nil.

Temp has now finished its job so we can re-set it to nil, temp:=nil; and get Head -> ('test') -> ('test2') -> Nil. The only pointer we need to always remember is head, because that indicates the beginning of the list. So this could be an array of two integers, but here is where pointers differ. They have no actual limit, like arrays, and we don't have to reserve extra memory than we need. Because when we declare an array with 12 positions for example those 12 spaces in memory are treated like they are used and if we only use 5 spaces for example we have wasted 7 spaces in memory (the heap). 

To go through the list and print information we can use a loop starting from the head until the end of the list. The loop could go like

var temp,previous:TPtrNode;

new(previous);

new(head);

temp:=head; { We start printing from the head }

while temp^.next <> nil do { While there are more pointers in the list }

   begin

      writeln(temp^.element);

      previous:=temp;

      temp:=temp^.next; { Temp is always re-set to the next element }

   end;

writeln(temp^.element);

 

So as you see the head is needed so we can start from there and move along the list. The loop checks if the next item is a pointer or nil. If there is a pointer it goes on to print the element inside, or else the loop stops. Note that the loop stops without printing the last element so we need to put a last writeln at the end. 

Deleting and searching uses a similar loop (I'm sure using this example you can think how they work) with the difference that we need to compare the elements to the element we are searching for. In the case of deleting, we need to keep track of the previous pointer of the one to be deleted, so when deleting we can make the previous pointer point to where the one we deleted used to point. So we would also need a variable var previous:TPtrNode;. So every time we loop, the previous pointer should be equal to temp (previous:=temp;) before temp is re-set to temp^.next. 

Knowing how difficult it is to understand these concepts when first introduced to them, I have created this java applet illustrating what I have described above. This applets allows you to add and remove information from a linked list using pointers. Note each time where head points to and how adding at the head or tail is different to adding between two pointers. Note also in deleting that the previous pointer could be pointing to nil if we are deleting the tail and after we have deleted a node we must dispose it so it is taken out of memory so we need to call dispose(temp);.

I have made the addition alphabetical so you can choose to add anywhere in the list and see how it works.

Email : vangliv@hotmail.com

To contact me: