Linked list

From Conservapedia

Jump to: navigation, search

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

Personal tools