Difference between revisions of "Linked list"
LouisPotts (talk | contribs) (IF THE BIBLE IS GOD'S BOOK WHY DIDN'T HE GIVE IT TO EVERYBODY R A T I O N A L W I K I) |
m (Reverted edits by LouisPotts (talk) to last revision by Ed Poor) |
||
| Line 1: | Line 1: | ||
| − | + | 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 language]]s, it is common to keep data in [[record]]s, thus: | |
| − | + | ||
| − | + | <code> | |
| + | record Employee | ||
| + | string[255] name; | ||
| + | integer age; | ||
| + | endrecord | ||
| + | </code> | ||
| + | |||
| + | The programmer can make a collection of records by adding a [[pointer]] field to each record, thus: | ||
| + | |||
| + | <code> | ||
| + | record EmployeeL | ||
| + | string[255] name; | ||
| + | integer age; | ||
| + | EmployeeL ^l; (* "l" for "link" *) | ||
| + | endrecord | ||
| + | </code> | ||
| + | |||
| + | 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: | ||
| + | |||
| + | <code> | ||
| + | record EmployeeLP | ||
| + | string[255] name; | ||
| + | integer age; | ||
| + | EmployeeL ^l; (* "l" for "link" *) | ||
| + | EmployeeL ^p; (* "p" for "prevlink" *) | ||
| + | endrecord | ||
| + | </code> | ||
| + | |||
| + | 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 [[DNA|genetic material]], or merely a set of [[dentist|dental]] [[X-ray]]s, 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]] [[algorithm]]s. 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 [[line]]ar 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]] | ||
| + | |||
| + | [[Category:Data structures]] | ||
Revision as of 05:12, February 29, 2012
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.