A linked list is a linear data structure in which each element, called a node, stores a value together with a reference to the next node, so that the elements form a chain instead of occupying one contiguous block of memory. Among data structures in programming, it is the classic alternative to the array: it trades fast access by index for constant-time insertion and removal at known positions.
The list is reached through a reference to its first node, the head. Following the chain of references from the head visits every element in order, and the last node points to nothing, usually represented as null or None.
How a linked list is organized
Each node is a small record allocated separately in memory. Because nodes are linked by pointers rather than by position, the list can grow and shrink one node at a time without copying existing elements, and nodes can live anywhere on the heap.
Inserting a new node after a known node takes two pointer updates: the new node points to the old successor, and the known node points to the new node. Removing a node similarly redirects one pointer around it. No other element moves, which is the main structural advantage of the linked list.
The common variants differ in how many references each node holds and how the ends are connected.
| Variant | Node references | Main advantage | Main cost |
|---|---|---|---|
| Singly linked list | Next only | Smallest memory overhead | Cannot move backward |
| Doubly linked list | Next and previous | Removal of a given node in constant time | Extra pointer per node |
| Circular linked list | Last node points to the first | Natural round-robin traversal | Care needed to stop loops |
| List with sentinel node | Dummy head or tail node | Fewer special cases for empty lists | One extra node |
| Skip list | Several levels of next pointers | Logarithmic search on average | More memory and complexity |
Time complexity of linked list operations
The performance of a linked list follows directly from its structure. Operations that start from a known node are constant time, O(1), while anything that must find a position first is linear time, O(n), because the list can only be walked node by node.
| Operation | Singly linked | Doubly linked with tail | Reason |
|---|---|---|---|
| Access by index | O(n) | O(n) | Nodes must be traversed in order |
| Search for a value | O(n) | O(n) | No ordering or index to exploit |
| Insert at head | O(1) | O(1) | Only the head pointer changes |
| Insert at tail | O(1) with tail pointer, else O(n) | O(1) | Tail reference avoids traversal |
| Remove a given node | O(n) to find predecessor | O(1) | Previous pointer is available |
| Concatenate two lists | O(1) with tail pointer | O(1) | Link the last node to the next head |
A frequent misunderstanding is that insertion in a linked list is always O(1). It is constant only once the position is known; inserting at index k still requires O(k) steps to reach that position.
Linked list compared with arrays and other structures
In theory, a linked list beats a dynamic array for insertions in the middle. In practice on modern hardware, dynamic arrays usually win for most workloads, because their elements sit next to each other in memory and benefit from CPU caches and prefetching, while each list node may cause a cache miss.
| Structure | Indexed access | Middle insertion | Memory locality |
|---|---|---|---|
| Linked list | O(n) | O(1) at a known node | Poor, nodes scattered |
| Dynamic array | O(1) | O(n), elements shift | Excellent, contiguous |
| Hash table | Not ordered by index | O(1) average by key | Moderate |
| Balanced tree | O(log n) with size data | O(log n) | Moderate |
Each node also carries pointer overhead: on a 64-bit system, one pointer takes 8 bytes, so a doubly linked list of small integers can use several times the memory of an array holding the same values, before counting allocator overhead.
Where linked lists are the right choice
Linked lists remain valuable where their specific guarantees matter: stable node addresses, constant-time splicing and cheap removal of an element that is already referenced. They also serve as building blocks for other structures, such as a stack or a queue, and as the chains inside hash tables with separate chaining.
| Situation | Recommended structure | Reason |
|---|---|---|
| Frequent access by position | Dynamic array | Constant-time indexing and cache efficiency |
| LRU cache with fast eviction | Doubly linked list plus hash table | Move or remove any entry in O(1) |
| Operating system kernel queues | Intrusive linked list | No extra allocation, stable addresses |
| Immutable data in functional languages | Singly linked list | New lists share their tails safely |
| Mostly appending and iterating | Dynamic array | Simpler and faster in practice |
An intrusive linked list stores the next and previous pointers inside the data objects themselves rather than in separate nodes, a technique widely used in operating system kernels to avoid extra allocations.
Common mistakes when implementing linked lists
- Losing the rest of the list: overwriting a node’s next pointer before saving the old successor disconnects every following node.
- Forgetting edge cases: empty lists, single-node lists and operations on the head or tail need explicit handling unless sentinel nodes are used.
- Memory leaks and dangling pointers: in languages without garbage collection, removed nodes must be freed exactly once and never used afterward.
- Accidental cycles: a wrong pointer can create a loop that makes traversal run forever; Floyd’s cycle detection finds such loops with two pointers.
- Recursive traversal of long lists: recursion over a list of millions of nodes can exhaust the call stack, so iteration is safer.
The simple explanation
A linked list is a chain of items where each item knows only the next one. To find the tenth item, you start at the first and follow the chain step by step.
It is like a treasure hunt with clues: each clue tells you where the next one is hidden. Adding a new stop is easy, because you only change one clue. Finding stop number ten quickly is hard, because you must follow every clue before it. The key takeaway is that linked lists make changes cheap and lookups slow.
How it is used in practice
A web service keeps the 10,000 most recently used product records in memory to avoid slow database queries. When the cache is full, it must remove the least recently used record, and every time a record is read, that record must move to the front.
The developers combine a hash table that maps product identifiers to nodes with a doubly linked list that keeps the records in order of use. A read finds the node through the hash table and moves it to the head with four pointer updates; an eviction removes the tail node. Both operations take constant time regardless of cache size, and database load drops noticeably because popular products stay cached.