As we have already noted, a linked list is a data structure which is either empty or has the following characteristics:
- there is a unique first node;
- every node except the first is the successor of exactly one other node;
- each node has at most one successor. This implies that:
- there are no loops;
- disconnected nodes are impossible;
- nodes with more than one successor are impossible:
- there is only one node (the last node) which has no successor.
A one-way linear list can be represented diagrammatically as follows:
For an empty list we simply write:
exlist is the list name and exav is the access variable which gives access to a specific node.
Next: Access Primitives