Linked List ADT

As we have already noted, a linked list is a data structure which is either empty or has the following characteristics:

  1. there is a unique first node;
  2. every node except the first is the successor of exactly one other node;
  3.  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:

LL4

For an empty list we simply write:

LL5

exlist is the list name and exav is the access variable which gives access to a specific node.

Next: Access Primitives