Skip to content
Velloreth
Programming 7 min read

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

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

OperationArrayLinked list
Access by indexO(1)O(n)
Search by valueO(n)O(n)
Insert at headO(n)O(1)
Insert at tailO(1) amortisedO(1) with tail pointer
Insert after a known nodeO(n)O(1)
Delete a known nodeO(n)O(1)
Memory per elementJust the valueValue 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.

Frequently asked questions

What is a linked list in simple terms?
A linked list is a chain of nodes where each node holds a value and a pointer to the next node. To reach the fifth item you start at the first and follow four pointers, which is why access is slower than an array but insertion is faster.
When should I use a linked list instead of an array?
Use a linked list when you insert and delete frequently at known positions, when you need stable references to nodes that survive other insertions, or when you are building a structure like an LRU cache. Use an array for almost everything else.
Why are linked lists often slower than arrays in practice?
Because of CPU cache locality. Array elements sit next to each other in memory, so the processor loads them in bulk. Linked list nodes are scattered, so each step is a cache miss, and that cost often outweighs the better Big-O.
What is the difference between a singly and doubly linked list?
A singly linked list has one pointer per node, to the next node, so you can only move forward. A doubly linked list also points to the previous node, which allows backward traversal and O(1) removal given only the node, at the cost of one extra pointer per node.
Can you binary search a linked list?
Not efficiently. Binary search needs O(1) access to the middle element, but reaching the middle of a linked list costs O(n), which removes the benefit. Use a sorted array or a balanced tree instead.
How do you detect a cycle in a linked list?
Use Floyd's tortoise and hare: advance one pointer one step and another two steps per iteration. If they ever meet, there is a cycle; if the fast pointer reaches the end, there is not. It runs in O(n) time and O(1) space.