Linked list
A linked list is a linear data structure that is composed of similar elements, all of which are typically related in some way; hence the term linked list. Traditional linked lists, in which the elements are all linked in some way, should be distinguished from Lisp's non-linked "lists", which can contain heterogeneous data.
In imperative programming languages, it is common to keep data in records, thus:
record Employee string[255] name; integer age; endrecord
The programmer can make a collection of records by adding a pointer field to each record, thus:
record EmployeeL string[255] name; integer age; EmployeeL ^l; (* "l" for "link" *) endrecord
Such a record collection is the canonical example of a linked list. In this example, since all of the records are singles, we term it a singly linked list. We can make the list more robust by adding a "Prev" field, pointing to the element before the current one, thus:
record EmployeeLP string[255] name; integer age; EmployeeL ^l; (* "l" for "link" *) EmployeeL ^p; (* "p" for "prevlink" *) endrecord
This collection of L/P records is a doubly linked list.
Applications
Linked lists are applicable in several ways. The first, most obvious application is data storage. For example, whether you have a large amount of decoded genetic material, or merely a set of dental X-rays, you will eventually need to store that data in a computer, and one possible way of doing that is to put it in a linked list.
A second, less obvious application is to the construction of fast sorting algorithms. Suppose you have a set of homogeneous records in memory, and need to put them in order. The problem can be restated as "Produce a total ordering over this set of records." Since each pair of elements in a non-cyclic linked list has exactly one predecessor and one successor, all you need to do to produce a total order over the set is to assign its members into a linked list, which can be done in linear time (O(n)). This is one of the fastest sorting algorithms known today, outstripped only by the hash table approach.
