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:
ii) disconnected nodes are impossible:
iii) nodes with more than one successor are impossible:
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:
For an empty list we simply write:
Stacks and Queues are specific types of linked lists.