5. Addressing a linked list

A linked list maintains the memory location of each item in the list by using a series of 'pointers' within the data structure.

A number of pointers are required, these are:

1. The 'start pointer' points to the first node in the list.
2. The last node in the list has a 'null pointer' (which is an empty pointer)
3. Each node has a pointer providing the location of the next node in the list.

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

A List data structure is to be used to store some names. The list is in alphabetic sort order.

The bare list looks like:

Task: Complete the linked list diagram.

Answer:

The first node is 'Alan' as this node is the first in alphabetic order. Alan node then points to Henry, which points to Paul which points to Sam. Sam is the last node in the list and so has a null pointer.

As each item is added to the list, the software must work out its relative position and adjust the pointer to suit.

An example sequence of loading the list might be

1. List is empty
2. Paul added to the list. Its pointer is null to also mark it as the last node. The start pointer also points to Paul
3. Alan is added. Now the start pointer needs to point to Alan since this name comes before Paul alphabetically
4. Sam is added. So the Paul pointer now points to Sam and Sam is given a Null pointer.
5. Henry is added. The Alan pointer is changed to point to Henry and the Henry pointer now points to Paul.