6. Inserting a node to a linked list

One of the basic algorithms needed to maintain the list is INSERT. This is explained by carrying on with the example from the previous page. But basically the INSERT algorithm adjusts the pointer of the relevant nodes to make sure the list remains in the correct order.

Example: Storing an alphabetic list of names in a linked list

The diagram above shows the final form of the linked list. But this must be built up step by step by using the list's INSERT algorithm.

An example sequence of loading the list might be to INSERT Paul, Alan, Henry and Sam in that order. Let's examine how the INSERT algorithm is used.

1. List is empty
2. Paul added to the list. Its pointer is null to mark it as the last node. The start pointer also points to Paul
3. Alan is added. Now the INSERT algorithm adjusts the start pointer of the list to point to Alan since this name comes before Paul. Paul remains the last node.
4. Sam is added. Sam comes after Paul, so the INSERT algorithm adjusts the Paul node pointer to Sam and the Sam node is given a Null pointer.
5. Henry is added. The INSERT algorithm of the list works out the Henry node needs to lie between the Alan and Paul nodes, so the Alan pointer is changed to point to Henry and the Henry pointer now points to Paul.
6. The linked list is complete.

In terms of a flow diagram the INSERT algorithm could be