Linked Lists

A linked list (also known as a one-way linear list) is a data structure which is either empty or has the following characteristics:

a) there is a unique first node;

b) every node except the first is the successor of exactly one other node;

c) each node has at most one successor. This implies that:

i) there are no loops, ie: the following is impossible:

LL1

ii) disconnected nodes are impossible:

LL2

iii) nodes with more than one successor are impossible:

LL3

iv) there is only one node (the last node) which has no successor.

Note that all of the above can exist as data structures, but they are not one-way linear lists.

A one-way linear list can be represented diagrammatically as follows:

LL4

For an empty list we simply write:

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

Stacks and Queues are specific types of linked lists.

Next: Stacks