How it works

The explanation, with examples you can run.

What they are good at

If you already hold a reference to a node, splicing next to it is O(1): point the new node at the old successor and point the old node at the new one. Removing is the same in reverse. A doubly linked list adds a prev pointer to every node so you can also remove a node without knowing its predecessor, and walk backwards.

That makes linked lists the right tool in a few real places:

LRU caches: a hash map from key to node, plus a doubly linked list ordered by recency. A hit unlinks the node and moves it to the front in O(1); eviction takes the node at the back.
Queues with unbounded growth that must never copy, and lists embedded inside other objects (the "intrusive" lists common in operating system kernels).
Immutable, shared lists in functional languages, where many lists share the same tail.

Here is the LRU pattern, with sentinel head and tail nodes so there are no special cases at the ends:

Your code

class LRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();                       // key -> node
    this.head = { prev: null, next: null };     // sentinel: most recent after it
    this.tail = { prev: this.head, next: null };
    this.head.next = this.tail;
  }
  unlink(node) { node.prev.next = node.next; node.next.prev = node.prev; }
  pushFront(node) {
    node.next = this.head.next; node.prev = this.head;
    this.head.next.prev = node; this.head.next = node;
  }
  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.unlink(node); this.pushFront(node);    // O(1): no searching, no shifting
    return node.value;
  }
  set(key, value) {
    if (this.map.has(key)) this.unlink(this.map.get(key));
    const node = { key, value };
    this.pushFront(node); this.map.set(key, node);
    if (this.map.size > this.capacity) {
      const oldest = this.tail.prev;
      this.unlink(oldest); this.map.delete(oldest.key);
    }
  }
  keys() { const out = []; for (let n = this.head.next; n !== this.tail; n = n.next) out.push(n.key); return out; }
}
const cache = new LRU(2);
cache.set("a", 1);
cache.set("b", 2);
cache.get("a");          // a is now the most recent
cache.set("c", 3);       // evicts b, the least recently used
console.log(cache.keys());   // [ 'c', 'a' ]

⌘/Ctrl + Enter

OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

A JavaScript Map remembers insertion order, so a simpler LRU can delete and re-insert keys instead. The linked list version is the one you will meet in other languages and in interviews.

Where they lose

There is no index, so list[k] means walking k nodes. Searching is a walk too. And every step of a walk is a pointer dereference to a node that may be anywhere in memory, which usually means a cache miss. Compare summing a million numbers stored both ways, with the nodes linked in a random order as they would be after a long-running program has inserted them over time:

Your code

⌘/Ctrl + Enter

OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

Both loops are O(n) and give the same sum. In Node 22 on a laptop the array took about 8 ms and the list between 750 and 1,000 ms. Each node also carries pointer and object-header overhead that an array of numbers doesn't have. This is why Java's ArrayList and ArrayDeque are usually recommended over LinkedList, and why Python's deque is built from blocks of 64 elements linked together rather than one node per item.

Check yourself

3 questions. Get them all right to finish this topic.

1.You need to insert into the middle of a sequence of a million items, and you only know the position by index. Which is faster in practice?
2.An LRU cache needs O(1) lookup by key and O(1) "move this entry to the front". What is the classic structure?
3.What does a doubly linked list add over a singly linked one?

0 of 3 right so far. Get all three to finish this topic.

Linked lists, and when they lose to arrays

How it works

What they are good at

Where they lose

Check yourself

Go deeper