Arrays vs Linked Lists: What's the Difference and When to Use Each

 Arrays and linked lists both store ordered collections of data, but they do it very differently under the hood — and that difference shows up constantly in interviews and in real performance bugs. Here's the easy-to-understand version.

---

Arrays: Data Sitting Next to Each Other

An array stores its elements in one continuous block of memory. Because every element is the same fixed distance apart, the computer can jump straight to any index instantly.

const fruits = ["apple", "banana", "cherry"];
console.log(fruits[1]); // "banana" — instant lookup, O(1)

The lookup is genuinely a single arithmetic operation. To find element i, the CPU computes base_address + (i × element_size) and reads that location. It doesn't matter whether you ask for index 2 or index 2,000,000 — same cost.

Strength: reading by index is O(1) — constant time.

Weakness: inserting or removing from the middle (or start) means shifting every element after it, which is O(n).

const items = [10, 20, 30, 40, 50];
items.splice(1, 0, 15);   // insert 15 at index 1
// Everything from 20 onward physically moves one slot right:
// [10, 15, 20, 30, 40, 50]

---

Linked Lists: Data Connected by Pointers

A linked list stores each element (called a node) separately in memory, with each node holding a pointer to the next one. There's no requirement that they sit next to each other.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

const first = new Node(12);
first.next = new Node(99);
// 12 -> 99 -> null

Strength: inserting or removing a node (once you have a reference to it) is O(1) — you just re-point a couple of links.

Weakness: to reach the 500th node, you have to walk through the 499 before it — there's no jumping straight to an index. Lookup is O(n).

---

A Working Linked List

Here's enough of an implementation to see where the O(1) and O(n) costs actually land:

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  // O(1) — no shifting, just a new head
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  // O(n) — must walk to the position first
  get(index) {
    let current = this.head;
    for (let i = 0; i < index && current; i++) {
      current = current.next;
    }
    return current ? current.value : undefined;
  }

  // O(1) once you hold the previous node
  removeAfter(node) {
    if (node && node.next) {
      node.next = node.next.next;
      this.size--;
    }
  }
}

Notice the asymmetry in removeAfter. The removal itself is one pointer assignment — genuinely constant time. But getting to the right node was O(n). This is the detail that trips people up: a linked list's O(1) insertion assumes you already have a reference to the right position.

---

Doubly Linked Lists

A singly linked list can only walk forward, which makes deleting a node awkward — you need its predecessor. A doubly linked list stores a prev pointer too:

class DoublyNode {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

// Remove a node in O(1) with only a reference to itself
function remove(node) {
  if (node.prev) node.prev.next = node.next;
  if (node.next) node.next.prev = node.prev;
}

The cost is one extra pointer per node — more memory, but true O(1) deletion given only the node. This is what makes LRU caches work.

---

Side-by-Side Comparison

• Access by index: Array O(1) vs Linked List O(n)

• Search for a value: Both O(n)

• Insert/delete at the start: Array O(n) vs Linked List O(1)

• Insert/delete at the end: Array O(1)* vs Linked List O(1) (with a tail pointer) or O(n) (without one)

• Insert/delete in the middle: Array O(n) vs Linked List O(1) given a node reference, O(n) to find it

• Memory layout: Array is contiguous; Linked List is scattered, linked by pointers

• Extra memory per element: Array: none; Linked List: one pointer per node (two if doubly linked)

*Amortized, assuming the array doesn't need to resize.

---

What "Amortized O(1)" Means

That asterisk deserves explaining, because it's a favourite interview follow-up.

A dynamic array (JavaScript's Array, Java's ArrayList, C++'s vector) has a fixed capacity under the hood. When you push past it, the runtime allocates a bigger block — usually double the size — and copies everything across. That single push costs O(n).

But because capacity doubles, those expensive copies get exponentially rarer. Spread across many pushes, the average cost per push works out to a constant. That's what amortized O(1) means: individual operations can be slow, but the average over a long sequence is constant.

---

The Thing Big O Doesn't Tell You: Cache Locality

On paper, inserting at the front of a linked list (O(1)) beats inserting at the front of an array (O(n)). In practice, for small and medium collections, the array often wins anyway. This surprises people.

The reason is memory hardware. CPUs don't read one byte at a time — they pull in a 64-byte cache line. When array elements sit next to each other, reading one element loads its neighbours for free, and the CPU's prefetcher sees the pattern and loads the next block before you ask. Iterating an array is close to the fastest thing a computer can do.

Linked list nodes are scattered across the heap. Each node.next is a jump to an unpredictable address, which the prefetcher can't anticipate. A cache miss costs roughly 100× a cache hit. So an O(n) memory copy of contiguous data frequently beats an O(1) pointer chase through scattered memory.

This is why real-world C++ and Rust codebases use vector/Vec far more than linked lists, and why "use a linked list for frequent inserts" is advice that needs benchmarking rather than assuming.

---

A JavaScript-Specific Caveat

Everything above describes arrays in the classical sense. JavaScript arrays are not quite that.

A JS array is really a special kind of object, and engines like V8 optimise it into a genuine contiguous block only when it stays "packed" — all elements present, consistent types, no gaps. Create a hole and the engine silently downgrades it to a slower dictionary-backed representation:

const packed = [1, 2, 3];
packed[10] = 11;       // creates holes at 3–9
// V8 may now treat this as a dictionary — O(1) index access is no longer guaranteed

delete packed[1];      // also creates a hole — use splice() instead

Keep arrays dense and type-consistent if you care about performance, and use splice() rather than delete to remove elements.

---

When Should You Use Which?

• Use an array when you mostly read by index, iterate in order, or care about memory efficiency — this covers most everyday JavaScript code (lists rendered in the UI, API response data, etc.). It should be your default.

• Use a linked list when you hold direct references to nodes and splice them in and out constantly, when you need stable references that survive insertions elsewhere, or when you're building another structure on top of it.

---

Where Linked Lists Genuinely Win

• LRU caches. A hash map plus a doubly linked list gives O(1) get, put, and eviction. The map finds the node; the list moves it to the front without shifting anything. This is a very common interview question (LeetCode 146).

• Browser history and undo/redo. Natural backward and forward traversal.

• OS schedulers and memory allocators. Free lists link blocks together with pointers stored inside the free blocks themselves.

• Hash table collision chains. Each bucket holds a short linked list of entries that hashed to the same slot.

---

Interview Questions to Expect

1. Reverse a linked list (LeetCode 206) — the canonical three-pointer problem.

2. Detect a cycle (LeetCode 141) — Floyd's fast-and-slow pointer technique.

3. Find the middle node — same two-pointer trick, one moving twice as fast.

4. Merge two sorted lists (LeetCode 21).

5. "Why not just use an array here?" — the question behind all the others. Answer with the trade-off, and mention cache locality if you want to stand out.

---

Conclusion

Neither structure is "better" — they trade fast lookups for fast inserts, or the reverse. Arrays give you constant-time indexing and excellent cache behaviour; linked lists give you constant-time splicing when you already hold the node.

In day-to-day application code, reach for an array by default. Reach for a linked list when you have a specific reason — usually that you're holding node references and restructuring constantly. Understanding that trade-off is exactly what interviewers are testing.

For the notation used here, see Big O Notation Explained. Next in this series: Stacks and Queues Explained.

Image: Derrick Coetzee / Pluke / Wikimedia Commons (Public domain)