# 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*.

**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. For more explanation, see Tim Rolfe's Searching in a Sorted Linked List.

* 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 Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries. Algorithms and Data Structures' explanation (Java and C++).
## More information

an introduction, a Java applet animation (Java).

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

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

Entry modified 23 May 2011.

HTML page formatted Tue Dec 6 16:16:32 2011.

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 May 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/linkedList.html