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 :

The advantage of a linked list is that the nodes can be accessed in order, even though they are not stored in order.

Example:

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

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

Adding a Node

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

The algorithm is ....

1. Store the NewNode in the next record.
2. Find PreviousNode by following links from StartPointer until the last node whose Town is before New Node.
3. Change the NewNode[Pointer] to PreviousNode[pointer] and change PreviousNode[pointer] to the address of the New Node..

In our example :

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).
 

The final linked list would be...

Linked lists with more pointers

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 :