linked list

(data structure)

Definition: A list implemented by each item having a link to the next item.

Also known as singly linked list.

Specialization (... is a kind of me.)
doubly linked list, ordered linked list, circular list.

Aggregate parent (I am a part of or used in ...)
jelly-fish, separate chaining.

See also move-to-front heuristic, skip list, sort algorithms: radix sort, strand sort.

Note: The first item, or head, is accessed from a fixed location, called a "head pointer." An ordinary linked list must be searched with a linear search. Average search time may be improved using a move-to-front heuristic or keeping it an ordered linked list, in which binary search may be effective; see below. An external index, such as a hash table, inverted index, or auxiliary search tree may be used as a "cross index" to help find items quickly.

Binary search may be effective with an ordered linked list. It makes O(n) traversals, as does linear search, but it only performs O(log n) comparisons.

A linked list can be used to implement other data structures, such as a queue, a stack, or a sparse matrix.

Author: PEB

Implementation

Bro. David Carlson's tutorial and code (C++). Maksim Goleta's C# Collections uses it to implement queue (C#). Algorithms and Data Structures' explanation (Java and C++). Alexander Georgiev's singly linked list (Java), including a merge and parallel merge sorts.

More information

An introduction.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 24 January 2022.
HTML page formatted Mon Jan 24 16:23:57 2022.

Cite this as:
Paul E. Black, "linked list", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 24 January 2022. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/linkedList.html