(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 demonstration.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Thu Oct 27 10:01:26 2005.
HTML page formatted Thu Oct 27 10:13:15 2005.
Cite this as:
Paul E. Black, "linked list", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/linkedList.html
