Linked lists appear in every data structures textbook and almost every coding interview, yet they appear in production application code surprisingly rarely. That gap exists for a reason: arrays are faster in practice for most access patterns. But linked lists are genuinely the right tool in specific situations — LRU caches, undo stacks, OS schedulers — and knowing why makes you a better engineer.
What changed in 2026
- LLM code assistants still suggest linked lists incorrectly. AI completions often propose linked-list solutions for problems where
Vec, ArrayList, or deque would be faster and simpler. Recognising the mismatch matters.
- Rust's
std::collections::LinkedList added a cursor API. The long-awaited stable cursor interface allows O(1) insert and delete at an arbitrary position without unsafe code. This makes Rust linked lists practically usable.
- Cache-friendly alternatives matured. Tiered arrays, slot maps, and arena allocators give linked-list-style flexibility with cache-friendly memory layout, and are now available in most ecosystems via crates/packages.
How a linked list works
Each node holds a value and a pointer to the next node (singly linked) or pointers to both neighbors (doubly linked).
from dataclasses import dataclass
from typing import Optional
@dataclass
class Node:
value: int
next: Optional["Node"] = None
# Build: 1 → 2 → 3 → None
head = Node(1, Node(2, Node(3)))
There is no underlying array. Nodes live wherever the allocator places them — which may be spread across heap memory.
Singly vs doubly linked
| Feature |
Singly linked |
Doubly linked |
| Memory per node |
value + 1 pointer |
value + 2 pointers |
| Traverse forward |
O(n) |
O(n) |
| Traverse backward |
Not possible |
O(n) |
| Delete at known node |
O(1) with prev pointer |
O(1) — has both neighbors |
| Use cases |
Stacks, forward-only queues |
LRU cache, deque, undo/redo |
Most production use cases need doubly linked lists. Singly linked lists are useful for purely stack-like or single-pass operations.
Time complexity
| Operation |
Linked list |
Array/Vec |
| Access by index |
O(n) |
O(1) |
| Insert at head |
O(1) |
O(n) — shift everything |
| Insert at tail |
O(1) with tail pointer |
O(1) amortised |
| Insert at known node |
O(1) |
O(n) — shift |
| Delete at known node |
O(1) |
O(n) — shift |
| Search |
O(n) |
O(n) unsorted / O(log n) sorted |
Linked lists win when you already hold a pointer to the target node and need to insert or delete. If you have to find the node first, the O(n) search negates the O(1) modification advantage.
The LRU cache pattern
The canonical real-world linked list application: a Least Recently Used (LRU) cache using a doubly linked list + hash map.
from collections import OrderedDict # CPython: doubly linked list + dict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key) # O(1): doubly linked pointer swap
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False) # O(1): evict LRU head
OrderedDict is internally a doubly linked list married to a hash map. move_to_end is an O(1) pointer re-link, not an O(n) shift.
Cache locality: why arrays win in benchmarks
Processor caches work by loading contiguous memory into cache lines (~64 bytes). An array stores elements side-by-side; iterating it is cache-friendly. Linked list nodes are scattered in heap memory; every next pointer dereference is a potential cache miss.
In practice, iterating 1 M integers:
- Array/Vec: ~2–5 ms (in-cache)
- Linked list: ~20–100 ms (cache misses dominate)
This gap exists even though both are O(n). The constant factor matters when n is large.
How to pick
- Do you need O(1) insert/delete at an arbitrary position and you hold a pointer to that position? → Linked list.
- Is this an LRU cache, undo stack, or ordered queue with frequent head/tail operations? → Doubly linked list (or
deque).
- Do you need random access by index? → Array.
- Are you iterating sequentially and performance matters? → Array (cache locality).
- Is the language Rust and you need interior mutability? → Consider a slot map or arena allocator for cache-friendly nodes.
Common mistakes
Losing the head pointer. If you re-assign head inside a loop without saving the original, you lose the list. Always keep a reference to the head.
Forgetting the tail pointer. Appending to a singly linked list without a tail pointer is O(n). Keep a tail reference for O(1) append.
Implementing linked lists in garbage-collected languages for performance. The GC must scan every node pointer, increasing GC pause time. Arrays are better for GC-heavy runtimes.
Circular list without a sentinel. Circular linked lists are easy to infinite-loop. Use a dummy sentinel node or Floyd's cycle detection during development.
What to skip
- Hand-rolled linked lists in Python, JavaScript, or Java for general use —
deque, arrays, and built-in queues are faster and safer.
- Linked lists for sorted data — you lose binary search. Use a balanced BST, skip list, or sorted array. See Binary search explained in 2026.
- Singly linked lists where you need deletion — without a previous-node pointer, deletion requires traversal. Use doubly linked or a different structure.
FAQ
Why do coding interviews focus so much on linked lists?
They test pointer manipulation, null handling, and in-place algorithms — skills that transfer to tree and graph problems. The structure is simple enough to implement on a whiteboard.
Is std::list in C++ a linked list?
Yes, it is a doubly linked list. std::deque and std::vector are usually faster for most uses. std::list is appropriate when you need stable iterators through frequent insertions/deletions.
What is a skip list?
A probabilistic data structure that layers multiple linked lists at different "express lane" intervals, achieving O(log n) search. Redis uses skip lists for sorted sets.
Can I reverse a linked list in place?
Yes — iterate once, swapping next pointers. O(n) time, O(1) space. It is a classic interview problem that tests pointer handling.
Where to go next