Array vs Linked List

Every complexity difference between an array and a linked list — which one wins at random access, which one wins at inserting at the front, why cache performance doesn't match the Big O on paper — traces back to one decision: where the elements actually live in memory. An array puts them all in one contiguous block. A linked list scatters them anywhere, holding the structure together with pointers instead of position. Everything else in this post is a consequence of that one choice.

The fundamental difference: contiguous vs scattered

An array is a single allocation — n elements sitting back to back in memory, so the address of element i can be computed directly: base + i × elementSize. A linked list is n separate allocations, each one a small node holding a value and a pointer to the next node's address. Nothing about a node's position in memory tells you anything about its position in the list — the only way to know what comes after a node is to already be holding it and read its next pointer.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null; // an address, not an offset — this is the whole structure
  }
}

Random access — O(1) vs O(n)

Because an array's addresses are computed, not discovered, reading arr[3] touches exactly one memory location no matter how large the array is — O(1). A linked list has no formula for "the address of index 3" — the only way to get there is to start at the head and follow next pointers one at a time, so reaching index k touches k + 1 nodes — O(n):

arr[3];                                // O(1) — computed address

function get(head, index) {              // O(n) — walked address
  let current = head, i = 0;
  while (current && i < index) {
    current = current.next;
    i++;
  }
  return current ? current.value : undefined;
}

This is also exactly why Heap Visualizer represents a heap as an array rather than a pointer-based tree: a heap needs to jump straight to a node's parent or children by index arithmetic (2i + 1, 2i + 2), and array access is what makes that O(1) instead of a traversal.

Insert or delete at the front — O(n) vs O(1)

Adding a value at the front of an array means every existing element has to physically shift one slot over to make room — there's no way to widen a gap at the start of one contiguous block without moving what's already there:

arr.unshift(newFirst);   // O(n) — every existing element moves up one slot

A linked list has no such block to preserve — prepending is just pointing a new node at the old head and updating what "head" refers to. Nothing else in the list moves at all:

function prepend(head, value) {
  const node = new Node(value);
  node.next = head;
  return node;              // O(1) — only the head reference changes
}

Insert or delete at the end — it depends on which pointer you kept

Array.prototype.push is amortized O(1) — most calls just write into already-reserved space, and the occasional internal resize is rare enough that its cost averages out (see Big O Notation Explained with Real Examples for how amortized analysis works). A singly linked list with no tracked tail has to walk the entire list to find the last node before it can append — O(n). Keep a tail pointer and appending drops back to O(1) — but removing the last node is still O(n) for a singly linked list, because relinking requires the second-to-last node, and a singly linked list can only walk forward. A doubly linked list (each node also holds a prev pointer) fixes that specific gap at the cost of a second pointer per node.

Insert or delete in the middle — same Big O, different bottleneck

Inserting at an arbitrary position looks like a tie on paper — both structures are O(n) overall — but the O(n) is spent on completely different work:

• Array: O(1) to reach the position (direct index), then O(n) to shift every element after it out of the way.
• Linked list: O(n) to reach the position by walking from the head, then O(1) to relink once you're there.

That distinction matters the moment you already hold a reference to the node — no walk required. This is the entire justification for a linked list showing up in a real system: an LRU cache pairs a hash map (for O(1) lookup of a node by key) with a doubly linked list (for O(1) removal and re-insertion of that exact node at the front, once found) — the hash map skips the traversal a plain linked list would otherwise force:

function removeNode(node) {           // O(1) — no traversal, we already hold it
  node.prev.next = node.next;
  node.next.prev = node.prev;
}

Cache locality — the gap Big O doesn't capture

Big O counts operations, not their real cost, and that gap is largest right here. A modern CPU doesn't fetch memory one value at a time — it pulls whole cache lines, and an array's contiguous layout means that once one element is loaded, its neighbors are typically already in cache too. A linked list's nodes can each be anywhere in memory, so walking next pointers is pointer chasing: the CPU frequently can't predict or prefetch the next address, forcing a fresh trip to main memory on nearly every step. Two traversals that are both "O(n)" on paper can end up measurably far apart in wall-clock time for exactly this reason — it's a large part of why arrays (or dynamic arrays — JS Array, Python list, C++ vector, Java ArrayList) are the default choice in practice even for operations where a linked list wins in theory.

Memory overhead

An array spends memory only on the values themselves (a dynamic array may over-allocate some extra capacity ahead of the next resize, trading space for that amortized O(1) push). Every linked list node spends extra memory on top of its value: at least one pointer (8 bytes on a 64-bit system) for a singly linked list, two for doubly linked — plus the bookkeeping overhead of each node being its own separate heap allocation, which an array entirely avoids by allocating once.

Cheat sheet

When each one actually wins

In practice, arrays (dynamic arrays specifically) are the default for nearly everything — cache-friendly, index-addressable, and what every high-level "list" type in a modern language is built on under the hood. JavaScript doesn't even ship a built-in linked list type, because Array already covers the overwhelming majority of real use cases. A genuine linked list earns its keep specifically when the access pattern is "I already hold the node, insert or remove it without shifting anything" — the LRU cache pattern above, certain queue/deque implementations, and undo/redo history where each step just needs to unlink from its neighbors. Even the tree-shaped structures on this site aren't all pointer-based for the same reason arrays win here: compare the Binary Search Tree Visualizer, which uses real left/right pointers because a BST's shape is unpredictable, against Heap Visualizer, which is array-backed because a heap's shape (always a complete tree) is predictable enough that index arithmetic replaces pointers entirely.

FAQ

Why doesn't JavaScript have a built-in linked list?

Because Array already covers what a linked list would offer for the vast majority of code, with better cache locality and no per-element pointer overhead. A hand-built linked list of plain objects in JS pays the pointer-chasing cost described above and the allocation overhead of each node being its own object — worse on both fronts than the array it's theoretically supposed to beat, unless the workload specifically needs O(1) insert/delete at a held reference.

Is a doubly linked list just strictly better than a singly linked one?

Not strictly — it fixes backward traversal and O(1) removal of a held node (including the tail) at the cost of a second pointer per node and twice the pointer-updating work on every insert or delete. Whether that trade is worth it depends entirely on whether the workload actually needs to walk or remove things backward.

Is a JS array really contiguous under the hood?

For a "packed" array of same-typed values (all numbers, say), V8 stores it as one contiguous backing buffer, matching the model in this post. Mixing types or leaving holes (sparse arrays) can push V8 into a slower, dictionary-based internal representation — a real-world wrinkle worth knowing, but a separate concern from the array-vs-linked-list complexity comparison here.

How does this apply in a coding interview?

Almost every linked-list interview question — reverse a list, detect a cycle, find the middle, merge two sorted lists — is really testing whether you can reason about pointers without an index to lean on. Naming the O(1)-front-insert / O(n)-random-access trade-off explicitly, the way Time Complexity Interview Guide recommends stating any complexity claim, is exactly the signal that framework is built to produce.