Doubly-linked lists are a special case of Multi-linked lists; it is special in two ways:
(FRED,19) (MARY,16) (JACK,21) (JILL,18)
I might want to order these elements alphabetically and also order them by age. I would have two pointers - NEXT-alphabetically, NEXT-age - and the list header would have two pointers, one based on name, the other on age.
Inserting into this structure is very much like inserting the same node into two separate lists. In multi-linked lists it is quite common to have back-pointers, i.e. inverses of each of the forward links; in our example this would mean that each node had four pointers.
A second very common use of multi-linked lists is sparse matrices. A sparse matrix is a matrix of numbers, as in mathematics, in which almost all the entries are zero. These arise frequently in engineering applications. the use of a normal Pascal array to store a sparse matrix is extremely wasteful of space - in an NxN sparse matrix typically only about N elements are non-zero. For example:
X = 1 2 3 ---------- Y=1 | 0 88 0 Y=2 | 0 0 0 Y=3 | 27 0 0 Y=4 | 19 0 66We can represent this by having linked lists for each row and each column. Because each node is in exactly one row and one column it will appear in exactly two lists - one row list and one column. So it needs two pointers: Next-in-this-row and Next-in-this-column. In addition to storing the data in each node, it is normal to store the co-ordinates (i.e. the row and column the data is in in the matrix). Operations that set a value to zero cause a node to be deleted, and vice versa. As with any linked list in practice is common for every pointer to have a corresponding back pointer.