Linked List
A linked list is a linear data structure in which elements (nodes) are stored at arbitrary memory locations, with each node containing a data field and one or more pointers linking it to adjacent nodes. Unlike arrays, linked lists do not require contiguous memory, enabling O(1) insertion and deletion at known positions without shifting elements, but they sacrifice O(1) random access (requiring O(n) traversal) and incur pointer overhead per node. Variants include singly linked lists, doubly linked lists, circular linked lists, and skip lists, each trading memory for specific operation efficiency.
Linked List Variants and Operation Complexities
| Variant | Pointers per Node | Insert/Delete (middle) | Reverse Traversal | Memory Overhead |
|---|---|---|---|---|
| Singly Linked | 1 (next) | O(1) if ref known, O(n) to find | No | Low (1 pointer) |
| Doubly Linked | 2 (next, prev) | O(1) if ref known | Yes | Medium (2 pointers) |
| Circular Singly | 1 (next, wraps) | O(1) if ref known | No | Low (1 pointer) |
| Circular Doubly | 2 (next, prev, wraps) | O(1) if ref known | Yes | Medium (2 pointers) |
| Skip List | Multiple levels | O(log n) expected | With extra pointers | High (O(n log n)) |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Array (data structure)
An array is a fundamental data structure that stores elements of the same type in contiguous memory locations, enabling O(1) random access via an integer index computed as base_address + index × element_size. Arrays are the basis for many higher-level structures (stacks, queues, heaps, hash tables) and are cache-efficient due to spatial locality. In advanced usage, multi-dimensional arrays, dynamic arrays (vectors), and circular arrays extend the basic model to support resizing, matrix operations, and efficient queue implementations.
Stack (data structure)
A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle, where elements are added (pushed) and removed (popped) only from one end called the top. Stacks support three primary operations: push (add element to top), pop (remove and return top element), and peek/top (inspect top element without removal), all in O(1) time. They are fundamental to function call management (call stack), expression evaluation (operator precedence, postfix notation), depth-first search, backtracking algorithms, and undo mechanisms in text editors.
Queue (data structure)
A queue is an abstract data type that follows the First-In-First-Out (FIFO) principle, where elements are added at the rear (enqueue) and removed from the front (dequeue), mirroring a real-world waiting line. All primary operations (enqueue, dequeue, front/peek) run in O(1) time when implemented with a circular array or doubly linked list. Queues are essential for breadth-first search, CPU and disk scheduling, inter-process communication (message passing), print spooling, and buffering in streaming and network protocols.
The term "linked list" was established in the late 1950s with the development of early AI programming languages. Allen Newell, Herbert Simon, and Cliff Shaw used linked memory structures in their 1955–1956 Logic Theorist program and later in IPL (Information Processing Language). The precise phrase "linked list" became standard with the LISP programming language (John McCarthy, 1958) where list processing was the central paradigm.