The data structure everyone learns for interviews and forgets by Monday — and why that's exactly backwards.
Here's the honest version of what most linked list tutorials skip:
You are almost certainly never going to write a linked list in JavaScript. Not in production. Not in a side project. Your language's built-in array already handles dynamic sizing, and it does it faster than a linked list in most cases, for reasons we'll get into. The interview circuit trained you to implement one on a whiteboard, and that's fine — but it created the wrong mental model. You walked away thinking linked lists are a data structure you might use. They're actually a data structure you need to understand — because they're hiding inside the tools you use every day, and knowing they're there changes how you reason about performance.
Your browser's back/forward navigation? Doubly linked list. Your text editor's undo history? Doubly linked list. The LRU cache inside every high-traffic web server, CDN, and database query optimizer? A doubly linked list fused with a hash map. Redis's LPUSH/RPUSH commands operate on a linked list. The Node.js event queue has linked list characteristics. The Linux kernel's process scheduler uses circular doubly linked lists internally.
They're not a relic. They're infrastructure. You just can't see them because they're one layer below where you usually work.
So let's learn them the right way — starting with the hardware, not the textbook.
Why Memory Layout Is the Whole Story
Before you write a single node, you need to understand the one thing that determines when a linked list wins and when it loses: cache locality.
Your CPU doesn't read from RAM one byte at a time. It's too slow for that — a RAM access takes 200–300 CPU cycles, while a cache hit takes 4. So the CPU plays a prediction game: when you access a memory address, it automatically pulls in the surrounding 64 bytes (a "cache line") on the assumption that you'll need nearby data next. This is called spatial locality, and it's why arrays are fast.
When you store an array of numbers, they sit next to each other in memory. When you loop over them, the CPU loads the first element — and gets the next 15 for free in the same cache line. It's reading ahead before you even ask.
Array in memory:
[ 10 | 20 | 30 | 40 | 50 | 60 ] → contiguous, cache-friendly
^ one cache fetch, all 6 loaded
A linked list destroys this. Each node is a separate heap allocation, scattered wherever the allocator found space. Following a next pointer means jumping to an arbitrary memory address — potentially on a completely different cache line, triggering a new RAM fetch, costing those 200–300 cycles, every single time.
Linked list in memory:
[10 | ptr] ──→ [20 | ptr] ──→ [30 | ptr]
0x1a04 0x7f82 0x3c11
(separate allocations, scattered across memory)
In practice, benchmarks consistently show linked list traversal running 10–100x slower than array traversal for large datasets — even though both are O(n) on paper. Big-O notation lies to you about this. It ignores constants, and the constant for "RAM access" is enormous on modern hardware.
This isn't a reason to dismiss linked lists. It's the reason to understand exactly when their advantages outweigh this cost. That answer is more specific than most tutorials admit.
Singly Linked List — The Minimal Form
A singly linked list is a chain of nodes where each node holds data and a pointer to the next node. That's it. No backward travel. No shortcuts.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// O(1) — we know exactly where the head is
prepend(value) {
const node = new Node(value);
node.next = this.head;
this.head = node;
this.size++;
}
// O(n) — must walk to the end
append(value) {
const node = new Node(value);
if (!this.head) {
this.head = node;
} else {
let current = this.head;
while (current.next) current = current.next;
current.next = node;
}
this.size++;
}
// O(n) — must walk to find it
delete(value) {
if (!this.head) return;
if (this.head.value === value) {
this.head = this.head.next; // drop the head, O(1)
this.size--;
return;
}
let current = this.head;
while (current.next) {
if (current.next.value === value) {
current.next = current.next.next; // skip the node, O(1) once found
this.size--;
return;
}
current = current.next;
}
}
toArray() {
const result = [];
let current = this.head;
while (current) {
result.push(current.value);
current = current.next;
}
return result;
}
}
Notice something about delete: finding the node is O(n), but the actual removal is O(1) — you just redirect one pointer. No shifting. No copying. No reorganizing memory. Compare that to an array, where deleting from the middle means shifting every subsequent element one position left — O(n) work even after you found the element.
This is the trade-off in one sentence: linked lists pay for access with their insertion/deletion advantage.
The singly linked list's natural shape is a stack — you push and pop from the head, both O(1), never need to go backward. It also fits a task queue where you only ever consume from one end.
What it genuinely can't do: random access. If you want the 500th element, you walk 500 nodes. There's no formula. This alone disqualifies singly linked lists from most use cases where you're searching or indexing.
Doubly Linked List — Where It Gets Actually Useful
Add a prev pointer to every node and something real changes: you can traverse in both directions, and — critically — you can remove a node in O(1) if you already have a reference to it.
class DNode {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null; // tail pointer makes append O(1)
this.size = 0;
}
// O(1) — we hold both ends
prepend(value) {
const node = new DNode(value);
if (!this.head) {
this.head = this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
this.size++;
}
// O(1) — tail pointer, no walking required
append(value) {
const node = new DNode(value);
if (!this.tail) {
this.head = this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.size++;
}
// O(1) — given the node directly, no searching required
removeNode(node) {
if (node.prev) node.prev.next = node.next;
else this.head = node.next; // it was the head
if (node.next) node.next.prev = node.prev;
else this.tail = node.prev; // it was the tail
node.next = node.prev = null;
this.size--;
}
// O(1) — both ends accessible instantly
removeHead() { if (this.head) this.removeNode(this.head); }
removeTail() { if (this.tail) this.removeNode(this.tail); }
}
The removeNode(node) method is the entire reason doubly linked lists exist in serious systems. When you have a direct reference to a node — not a value you need to search for, but the actual node object — deletion is just pointer surgery. Four pointer updates. Done.
This changes everything for the use case that actually matters.
The One Pattern Where Linked Lists Are Irreplaceable
The LRU (Least Recently Used) cache is the canonical real-world use case — and it's worth understanding in detail because it appears in CDN edge nodes, database query planners, CPU cache replacement policies, DNS resolvers, and web server in-memory caches.
The problem: you have a cache with limited capacity. When it's full and you need to add something new, you evict the item that was accessed least recently. You need:
- O(1) lookup: "Is this key in the cache?"
- O(1) insert: "Add this new key-value pair"
- O(1) eviction: "Remove the least recently used item"
- O(1) promotion: "This key was just accessed, move it to 'most recently used'"
An array can't do this. When you access an item, you need to move it to the "recently used" position — that's O(n) shifting. A hash map alone can't do it either — it has no concept of order.
The solution is a doubly linked list paired with a hash map:
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // key → node (O(1) lookup)
this.list = new DoublyLinkedList(); // ordered by recency
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this.list.removeNode(node); // O(1) — we have the node directly
this.list.prepend(node.value); // O(1) — move to head (most recent)
this.map.set(key, this.list.head);
return node.value.val;
}
put(key, val) {
if (this.map.has(key)) {
this.list.removeNode(this.map.get(key)); // O(1)
} else if (this.list.size >= this.capacity) {
// evict the tail — it's the least recently used
this.map.delete(this.list.tail.value.key);
this.list.removeTail(); // O(1)
}
this.list.prepend({ key, val }); // O(1)
this.map.set(key, this.list.head);
}
}
Every operation is O(1). The hash map gives instant lookup. The doubly linked list maintains order and provides O(1) removal because we store the node reference in the hash map — we never search for the node, we go directly to it.
This is the move that makes the whole structure work. The hash map stores node references, not values. When we access a key, we pull the node directly out of the middle of the list and move it to the head — no traversal. That's only possible with a doubly linked list where removeNode doesn't require knowing where the node is in the sequence.
The Honest Comparison
Most tutorials give you a comparison table. Here's one that's actually honest about modern hardware:
| Operation | Array | Singly LL | Doubly LL |
|---|---|---|---|
| Access by index | O(1) | O(n) | O(n) |
| Search by value | O(n) | O(n) | O(n) |
| Insert at head | O(n) — shift all | O(1) | O(1) |
| Insert at tail | O(1) amortized | O(n) or O(1) w/ tail ptr | O(1) w/ tail ptr |
| Delete at head | O(n) — shift all | O(1) | O(1) |
| Delete in middle (by value) | O(n) find + O(n) shift | O(n) find + O(1) remove | O(n) find + O(1) remove |
| Delete by node reference | — | — | O(1) ← the whole game |
| Memory per element | Low (just data) | Medium (+1 pointer) | Higher (+2 pointers) |
| Cache performance | Excellent | Poor | Poor |
| Traversal speed in practice | ~10–100x faster | Slow | Slow |
The "delete by node reference" row is the one that matters. It's the entire reason doubly linked lists exist in production systems. Everything else, arrays do better or equal for most workloads — because of cache locality, not because of Big-O.
If you're choosing between array and linked list for a problem where you're iterating through data, an array wins even if your Big-O analysis says they're equal. The constant factor of cache performance is that significant.
When to Actually Use Each One
Reach for a singly linked list when:
- You're building a stack and want textbook clarity (though an array works fine here too)
- You're implementing something where you only ever add/remove from one end
- Memory is extremely tight and you can't afford the extra
prevpointer
Reach for a doubly linked list when:
- You need O(1) deletion and you'll have direct node references (LRU cache, undo history where each action holds its own node)
- You're building anything that requires backward traversal without a second pass
- You're implementing a deque (double-ended queue) with O(1) operations at both ends
Don't reach for either when:
- You're just storing and iterating over data — use an array
- You need frequent random access — use an array
- You're searching by value — use a hash map or sorted array with binary search
The deeper point: linked lists are most valuable not as standalone structures but as the ordered component inside composite structures. The LRU cache doesn't use a linked list instead of a hash map — it uses them together. That combination produces something neither could achieve alone. That's the real lesson.
Where They're Already Running in Your Stack
Without writing a single line of linked list code, these structures are running around you right now:
Node.js — The timers module maintains doubly linked lists to track setTimeout/setInterval expiry. The http module uses them for connection pools.
V8 (Chrome's JS engine) — The garbage collector uses linked list-like structures to track object generations and manage the free list of available memory blocks.
Redis — LPUSH/RPUSH/LPOP/RPOP operate on a linked list. Redis lists are actually a hybrid (ziplist for small sizes, linkedlist for large), but the interface is a linked list.
Linux kernel — The process scheduler's run queue is a doubly linked list. The list_head structure in the kernel source is one of the most used data structures in any OS codebase.
Your browser's navigation — Every window.history.back() and window.history.forward() is a doubly linked list traversal.
You've been using linked lists constantly. You just didn't know their name.
The Real Reason to Learn This
Interview prep is the wrong motivation to learn linked lists. The right motivation is this: understanding why a doubly linked list paired with a hash map gives you O(1) everything for an LRU cache — that kind of reasoning is what separates engineers who design systems from engineers who just implement requirements.
When someone at a senior system design interview says "we need an LRU cache with O(1) get and put" and you immediately know the structure — and, more importantly, you know why that structure works at the hardware level — that's not trivia. That's thinking.
The data structure is simple. The thinking behind it isn't.
Code examples are in JavaScript for readability. The concepts apply identically in Python, Go, Rust, or any other language. In production systems you'd typically use the language's built-in deque or list structures rather than rolling your own — but understanding the internals is exactly the point.
Cheers !
Top comments (1)
Following your own cache-locality point one more step lands somewhere fun: that LRU's doubly linked list is doing the exact pointer chasing you spent the first half of the post warning about. Every get() hops to a node scattered somewhere on the heap just to splice it out. That's why a lot of production LRUs skip real node objects entirely. They back the "list" with a flat array and store next and prev as integer indices into it, so you keep the O(1) splice but the nodes sit contiguous and the prefetcher stays happy. Same algorithm, none of the cache misses. Felt like the natural ending to the argument you were already making.