| Line 1: |
Line 1: |
| − | IF THE BIBLE IS GOD'S BOOK WHY DIDN'T HE GIVE IT TO EVERYBODY
| + | 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. |
| − | IF THE BIBLE IS GOD'S BOOK WHY DIDN'T HE GIVE IT TO EVERYBODY
| + | |
| − | IF THE BIBLE IS GOD'S BOOK WHY DIDN'T HE GIVE IT TO EVERYBODY
| + | In [[imperative]] [[programming language]]s, it is common to keep data in [[record]]s, thus: |
| − | IF THE BIBLE IS GOD'S BOOK WHY DIDN'T HE GIVE IT TO EVERYBODY
| + | |
| − | IF THE BIBLE IS GOD'S BOOK WHY DIDN'T HE GIVE IT TO EVERYBODY
| + | <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]] |