(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.
See also move-to-front heuristic, 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. 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.
A linked list can be used to implement other data structures, such as a queue, a stack, or a sparse matrix.
Author: PEB
an introduction, a Java applet animation (Java).
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 3 August 2009.
HTML page formatted Mon Aug 3 10:37:32 2009.
Cite this as:
Paul E. Black, "linked list", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 3 August 2009. (accessed TODAY)
Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/linkedList.html
