19
edits
Changes
Jump to navigation
Jump to search
New page: In computer science, the invented term '''linked list''' refers to a linear data structure that is composed of similar elements, all of which are typically related in some way; hen...
In [[computer science]], the invented term '''linked list''' refers to 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 [[The Greatest Commandment|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;
EmployeeL ^p;
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]]
In [[The Greatest Commandment|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;
EmployeeL ^p;
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]]