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.

See also

• Data structure
• Array
• List
• Binary tree