(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 or a stack.
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 23 April 2007.
HTML page formatted Mon Apr 23 09:23:15 2007.
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. 23 April 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/linkedList.html
