Linked Lists Explained: When They Beat Arrays
Linked lists store elements in nodes connected by pointers. Learn singly and doubly linked lists, their real costs, and when they actually beat arrays.
By Velloreth
What a linked list is
A linked list is a sequence of nodes where each node stores a value and a reference to the next node. The list itself is just a pointer to the first node, called the head.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
That is the entire structure. There is no array underneath, no contiguous block of memory. Each node is allocated wherever the allocator finds room, and the pointers stitch them into a sequence.
This design is the source of both the linked list’s advantages and its problems.
The costs
| Operation | Array | Linked list |
|---|---|---|
| Access by index | O(1) | O(n) |
| Search by value | O(n) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert at tail | O(1) amortised | O(1) with tail pointer |
| Insert after a known node | O(n) | O(1) |
| Delete a known node | O(n) | O(1) |
| Memory per element | Just the value | Value plus one or two pointers |
The pattern is clear. Arrays win on access. Linked lists win on insertion and deletion given a reference to the node.
That qualifier is doing a lot of work. Inserting at position 500 in a linked list still costs O(n), because you must walk from the head to reach position 500. The O(1) only applies when you already hold the node you want to insert after.
Why arrays usually win anyway
Here is the part that textbooks often skip: in real programs, arrays beat linked lists for most workloads, even where the Big-O favours the list.
The reason is CPU cache locality. Modern processors do not read single bytes from RAM; they read cache lines of 64 bytes. When you iterate an array, the first access pulls in the next several elements for free, so the following iterations hit the cache. When you iterate a linked list, each node is somewhere else in memory, so nearly every step is a cache miss that costs on the order of a hundred cycles.
The practical consequence: iterating an array of a million integers can be several times faster than iterating a linked list of the same million integers, despite both being O(n). The constant factor that Big-O discards is exactly the factor that dominates here.
This is why modern languages lean on arrays. JavaScript’s Array is a dynamic array. Python’s list is a dynamic array. Go’s slice is a dynamic array. Rust’s Vec is a dynamic array. The linked list is in the standard library, but it is rarely the default choice.
Singly vs doubly linked lists
A singly linked list has one pointer per node, to the next node. You can only move forward.
A doubly linked list adds a prev pointer:
class DoublyNode {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
The extra pointer buys two things:
- Backward traversal — you can walk the list in reverse.
- O(1) removal given only the node — with a singly linked list, deleting a node requires its predecessor, which means walking from the head. With a doubly linked list, the node knows its predecessor.
The cost is one extra pointer per node, which is significant when values are small. A doubly linked list of 32-bit integers spends two-thirds of its memory on pointers.
Where linked lists genuinely win
Despite the cache argument, there are places where linked lists are the right answer.
LRU caches. The classic implementation pairs a hash map with a doubly linked list. The map gives O(1) lookup; the list maintains recency order with O(1) moves. Neither structure alone can do both.
// Conceptual shape of an LRU cache
// map: key -> node
// list: most-recently-used at head, least at tail
// get(key): move node to head
// put(key, value): insert at head, evict tail if over capacity
Stable node references. If you hand out references to elements and then insert more elements, array indices shift and references break. Linked list nodes stay valid. This matters in editors, schedulers, and any structure where external code holds handles.
Adjacency lists in graphs. A graph’s neighbours are naturally a list, and you rarely need random access to them.
Free lists and memory pools. Allocators keep freed blocks in a linked list because insertion and removal are O(1) and order does not matter.
Merging and splitting. Splicing two linked lists together is O(1) pointer surgery. Doing the same with arrays means copying.
Common operations
Reversing a singly linked list
This is the canonical interview question, and it is worth understanding because it exercises pointer discipline.
function reverse(head) {
let prev = null;
let current = head;
while (current) {
const next = current.next; // save before overwriting
current.next = prev; // flip the pointer
prev = current; // advance prev
current = next; // advance current
}
return prev; // new head
}
The trick is saving current.next before overwriting it. Forgetting that line is the most common bug.
Detecting a cycle
Floyd’s tortoise and hare uses two pointers moving at different speeds:
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
If there is a cycle, the fast pointer eventually laps the slow one. If there is not, the fast pointer reaches the end. O(n) time, O(1) space — much better than the naive approach of storing every visited node in a set.
Finding the middle
The same two-pointer idea finds the middle in one pass:
function middle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
When the fast pointer reaches the end, the slow pointer is halfway.
The sentinel node trick
Many linked list bugs come from special-casing the head — inserting at the front, deleting the first element, and so on. A sentinel (or dummy) node removes the special cases:
function removeValue(head, target) {
const dummy = new Node(null);
dummy.next = head;
let current = dummy;
while (current.next) {
if (current.next.value === target) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return dummy.next;
}
Because the dummy node always exists, every deletion has a predecessor, and the head is no longer a special case. This one technique eliminates most linked list edge-case bugs.
When to reach for one
Use a linked list when:
- You insert and delete frequently at positions you already hold.
- You need references to nodes that stay valid across other insertions.
- You are building an LRU cache, a free list, or a queue with O(1) removal at both ends.
- You are splicing large sequences together.
Use an array when:
- You access by index.
- You iterate over everything, which is most of the time.
- You care about memory overhead and cache performance.
- You are unsure — the array is the safer default.
For the broader picture of how these choices fit together, see data structures every developer should know and Big-O notation explained. If you are working through interview problems, debugging strategies that work covers the reasoning process that matters more than memorised solutions.
Quotable summary
A linked list stores each element in a node that also holds a pointer to the next node, so elements need not be contiguous in memory. It gives O(1) insertion and deletion given a reference to the node, but O(n) access by index. In practice arrays outperform linked lists for most workloads because contiguous memory is cache-friendly, and the constant factor Big-O discards is the one that dominates. Linked lists remain the right choice for LRU caches, stable node references, adjacency lists, free lists, and sequence splicing. A doubly linked list adds a previous pointer for backward traversal and O(1) removal given only the node, at the cost of one extra pointer per element.