Home  Back Topics CD Orders  INDEX 
Linked List

Each record in the list is called a node.

Each node has a field which is a pointer to the next node in the linked list (ie its address). The last node has a null pointer.

There is a Start Pointer which links to the first node of the list.

There may also be a Next Free Pointer giving the address of the next free record space.

Graphical representation of a Linked List :

Example:

The linked list shown has been assigned pointers after a sorting process -

Address Town Pointer
1 Bridgend 4
2 Swansea 5
3 Reading 2
4 Cardiff 3
5 Swindon 0
6    
7    
8    
Start Pointer = 1
Next Free Pointer = 6

By following the links, the records can be accessed in alphabetical order.

A better system is to use two linked lists - one to link all the free spaces together -

Address Town Pointer
1 Bridgend 4
2 Swansea 5
3 Reading 2
4 Cardiff 3
5 Swindon 0
6   7
7   8
8   0
Start Pointer = 1
Next Free Pointer = 6

 
 

Adding a Node

Suppose we wanted to add the node 'Pembroke' to the above linked list.

The algorithm is ....

1. Add the New Node at the address NFP and update NFP to NFP[Pointer].
2. Find Previous Node by following links from SP until the last node whose Town is less than New Node.
3. Change the New Node[Pointer] to Previous Node[pointer] and change Previous Node[pointer] to the address of the New Node..

Confused!!???...

Applying each step to our example :

Address Town Pointer
1 Bridgend 4
2 Swansea 5
3 Reading 2
4 Cardiff 3
5 Swindon 0
6   7
7   8
8   0
Start Pointer = 1
Next Free Pointer = 6

 

Step 1.

Add the New Node at the address NFP and update NFP to NFP[Pointer].

The NFP is 6 and that node's pointer is 7, so we enter 'Pembroke' at node 6, and change the NFP to be 7.

(The free space linked list is now correct)

 Address Town Pointer
1 Bridgend 4
2 Swansea 5
3 Reading 2
4 Cardiff 3
5 Swindon 0
6 Pembroke 7
7   8
8   0
Start Pointer = 1
Next Free Pointer = 7

 

Step 2.

Find Previous Node by following links from SP until the last node whose Town is less than New Node.

Links are Bridgend - Cardiff - and we stop there because the next node (Reading) comes after 'Pembroke'.

So Previous Node is 4.(Cardiff)

 Address Town Pointer
1 Bridgend 4
2 Swansea 5
3 Reading 2
4 Cardiff 3
5 Swindon 0
6 Pembroke 7
7   8
8   0
Start Pointer = 1
Next Free Pointer = 7

 

Step 3.

Change the New Node[Pointer] to Previous Node[pointer]

so Pembroke's pointer is 3

and change Previous Node[pointer] to the address of the New Node.

..so Cardiff's pointer becomes 6.

 Address Town Pointer
1 Bridgend 4
2 Swansea 5
3 Reading 2
4 Cardiff 6
5 Swindon 0
6 Pembroke 3
7   8
8   0
Start Pointer = 1
Next Free Pointer = 7

 

 

Deleting a node

Suppose we now want to delete the node 'Swansea'

The algorithm is as follows...

1. Follow the pointers until the Deleted Node (Swansea) is found, and make a note of the Previous Node (Reading).
2. Change the Previous Node's (Reading's) pointer to the Deleted Node's (Swansea's) pointer(5).
3. Change the Deleted Node's (Swansea's) pointer (5) to the NFP (7) and the NFP[pointer] (7) to the Deleted Node's address(2).

The final linked list would be...

Address Town Pointer
1 Bridgend 4
2 Swansea 7
3 Reading 5
4 Cardiff 6
5 Swindon 0
6 Pembroke 3
7   8
8   0
Start Pointer = 1
Next Free Pointer =2

Notice that the node 'Swansea' is still physically stored but is part of the free nodes list and will be overwritten by the first newly added node.

 

 

It is quite possible to include a number of pointer fields in each record. Our example could contain another linked list which gives the train stations in the order in which they would occur travelling from Pembroke to London :

Address Town Ptr1 Ptr2
1 Bridgend 4 4
2 Swansea 5 1
3 Reading 2 0
4 Cardiff 6 5
5 Swindon 0 3
6 Pembroke 3 2
7   8 8
8   0 0
Start Pointer (alphabetical)= 1
Start Pointer (train stations)= 6
Next Free Pointer =7

 

 

NOTES :

When records are sorted they are not physically moved. Only the pointers are altered.

There are also...

Circular linked lists - where the last item links back to the first one.

Two-way linked lists - where each node has two pointers. One to the next node and one to the previous node.

and of course.....Two-way circular linked lists.