Linked Lists

What is it?

An array keeps its items packed tightly together in memory, which is fast to read but expensive to insert into. A linked list takes a different approach: each item (called a node) stores its value plus a pointer to the next node. The items don't need to sit next to each other in memory at all — they're connected purely through these pointers.

This trade-off is the opposite of an array's: inserting or removing a node is fast (you just change a couple of pointers), but finding the 5th item means walking through the first four nodes one by one — there's no shortcut to "jump" straight to a position.

Explain like I'm 10

A linked list is like a scavenger hunt: each clue tells you where to find the next one. You can't jump straight to clue #5 — you have to follow the chain from the start. But inserting a brand-new clue into the middle is easy: just point the previous clue somewhere new.

Examples

A simple linked list in JavaScript

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

const first = new Node(10);
const second = new Node(20);
first.next = second; // 10 → 20

console.log(first.value);      // 10
console.log(first.next.value); // 20

How it works

Each node holds a value and a reference to the next node (or null if it's the last one). To read the item at position 5, you must start at the first node and follow .next five times — there's no way to calculate its memory location directly, unlike an array.

[10] → [20] → [30] → null
 head

To reach 30: head → next → next

Why does it exist?

Linked lists shine when your program does a lot of inserting and removing (especially at the front or in the middle) and doesn't need fast random access by position. They're also the foundation for other structures, like stacks and queues.

When to use it

Reach for a linked list when your program does a lot of inserting and removing — especially at the front or in the middle of a collection — and doesn't need to jump to an arbitrary position by index.

When not to use it

If you need frequent random access by index (get the 500th item), a linked list is a poor fit — that's O(n) here, versus O(1) for an array. In practice, plain arrays cover most everyday JavaScript needs; reach for a linked list mainly when building another structure (a queue, a stack) or solving a problem that specifically calls for one.

Common mistakes

• Forgetting to update the next pointer when inserting a node, accidentally breaking the chain.

• Losing the reference to the rest of the list by overwriting a next pointer before saving it elsewhere.

• Assuming linked lists have fast random access like arrays do — they don't.

Practice exercises

1. Easy:

   Build a linked list of 3 nodes manually and print each value by following .next.

2. Medium:

   Write a function that returns the length of a linked list by traversing it.

3. Hard:

   Write a function that reverses a singly linked list in place, without creating a new list.

Interview questions

What's the main trade-off between arrays and linked lists?

Arrays offer fast random access (O(1)) but slow insertion/removal in the middle (O(n)), since later elements must shift. Linked lists offer fast insertion/removal (O(1), given a reference to the node) but slow access by position (O(n)), since there's no way to jump directly to an index.

What is a node?

The basic unit of a linked list — an object holding a value and a pointer (or pointers) to neighboring nodes.

What's the difference between a singly and doubly linked list?

A singly linked list's nodes only point to the next node, so it can only be traversed forward. A doubly linked list's nodes also point to the prev node, allowing traversal in both directions at the cost of one extra pointer (and its upkeep) per node.

Why is inserting at the front of a linked list O(1), while inserting at the front of an array is O(n)?

Inserting at the front of a linked list just means creating a new node and pointing it at the old head — nothing else moves. Inserting at the front of an array requires shifting every existing element one slot to the right to make room, which touches all n elements.

Why is finding the nth element O(n) in a linked list but O(1) in an array?

An array can compute an element's memory address directly from its index (base address + index × element size). A linked list has no such formula — the only way to reach the nth node is to follow next pointers one at a time from the head.

What is a circular linked list, and what's it useful for?

A linked list where the last node's next points back to the first node instead of to null, forming a loop. It's useful for things that naturally cycle, like round-robin task scheduling or a repeating playlist, where you want to keep advancing without ever hitting an end.

What is Floyd's cycle detection algorithm, and how does it detect a cycle using O(1) extra space?

Also called the 'tortoise and hare': walk two pointers through the list, one (slow) moving one node at a time and the other (fast) moving two nodes at a time. If the list has a cycle, fast will eventually enter the loop and lap slow, and the two pointers will land on the same node. If the list has no cycle, fast simply reaches null first. Only two pointers are used, regardless of list length, so the space cost is O(1).

Why must the fast and slow pointers eventually meet if there's a cycle, instead of just missing each other forever?

Once slow enters the cycle, both pointers are moving within a loop of fixed length. Each step, fast closes the distance to slow by exactly one node (it gains 2 but slow also advances 1). Since the gap shrinks by 1 every step and wraps around a finite loop, it must eventually hit 0 — they can't perpetually skip over each other.

Once Floyd's algorithm finds a meeting point, how do you find the exact node where the cycle begins?

Reset one pointer to the head of the list, leave the other at the meeting point, and advance both one node at a time. The two pointers will meet again exactly at the start of the cycle — this works because of the distance relationship between the head, the cycle's start, and the meeting point that falls out of the earlier steps.

Walk through reversing the list `1 -> 2 -> 3 -> null` iteratively using three pointers (`prev`, `current`, `next`).

Start with prev = null, current = head (node 1). Each iteration: save next = current.next, then point current.next = prev (reversing the link), then move both prev = current and current = next forward. After processing node 1: list is 1 -> null, prev=1. After node 2: 2 -> 1 -> null, prev=2. After node 3: 3 -> 2 -> 1 -> null, prev=3, current=null — loop ends and prev is the new head.

How would you reverse a singly linked list recursively, and how does its complexity compare to the iterative version?

Recurse to the end of the list first, then, as each call returns, point the next node's next back at the current node and set the current node's next to null. Both approaches are O(n) time, but the recursive version uses O(n) extra space for the call stack, while the iterative version uses only O(1) extra space.

What's a common bug when reversing a linked list iteratively?

Overwriting current.next to point at prev before saving the original current.next somewhere first — once overwritten, there's no way to reach the rest of the original list, so the reversal silently truncates it.

What is a sentinel (dummy) head node, and why does it simplify list code?

A placeholder node kept permanently at the front of the list, before the real head, whose value is never used. It means the 'real' first node is always some node's .next rather than the list's own head reference, so inserting or removing at the front no longer needs special-cased logic separate from insertions/removals elsewhere in the list.

How would you find the middle node of a linked list in a single pass, without first counting its length?

Use slow and fast pointers starting at the head: advance slow one node per step and fast two nodes per step. When fast reaches the end (or null), slow is sitting on the middle node, because it has covered exactly half the distance fast has.

Why does a queue built on a singly linked list need both a `head` and a `tail` pointer to keep both operations O(1)?

Dequeuing from the front only ever needs head. But enqueuing at the back, without a tail pointer, would require traversing the entire list from head to find the last node — making enqueue O(n). Keeping a tail pointer lets a new node be attached directly, in O(1).

What's a subtle bug when removing a node from the middle of a singly linked list?

You can't remove a node using only a reference to that node itself — you need a reference to the previous node, since removal means updating the previous node's next to skip over the one being removed. Forgetting to track the previous node while traversing is a common cause of broken removal logic.

There's a trick to 'delete' a node given only a reference to it (no access to the previous node): copy the next node's value into it, then skip over the next node. Why does this fail for the last node in the list?

The trick works by making the target node effectively become its successor, then removing the now-duplicated successor. But the last node has no successor to copy from or skip over — there's nothing after it to borrow a value from, so the trick has no next node to fall back on.

How would you find where two singly linked lists intersect (merge into a shared tail), in O(n + m) time and O(1) extra space?

Walk both lists to find their lengths, advance the pointer on the longer list by the length difference so both pointers have the same remaining distance to the end, then advance both together one node at a time — the node where they become equal (same reference) is the intersection point.

How would you remove the nth node from the end of a linked list in a single pass?

Advance a fast pointer n nodes ahead of a slow pointer (both starting at a dummy head before the real head), then move both forward together until fast reaches the end. At that point, slow is sitting right before the node to remove, so slow.next = slow.next.next removes it.

How would you merge two already-sorted linked lists into a single sorted list, and what's the time complexity?

Walk both lists with two pointers, repeatedly attaching whichever current node has the smaller value to the result and advancing that list's pointer; once one list runs out, attach the rest of the other directly. This is O(n + m) time, since each node from both lists is visited exactly once, and O(1) extra space if you re-link existing nodes rather than creating new ones.

How would you check whether a linked list is a palindrome, ideally using O(1) extra space?

Find the middle with slow/fast pointers, reverse the second half in place, then walk the first half and the reversed second half together comparing values. If they match all the way through, it's a palindrome. This avoids the O(n) space an array copy would cost, at the cost of temporarily mutating (and optionally restoring) the list.

What's the extra memory cost of a doubly linked list compared to a singly linked list, per node?

One additional pointer per node (prev), typically 8 bytes on a 64-bit system, plus the ongoing cost of keeping that pointer correctly updated on every insertion and removal.

Why do a doubly linked list and a hash map together form the backbone of a classic LRU cache implementation?

The hash map gives O(1) lookup from a key to its node. The doubly linked list keeps nodes ordered by recency and, because each node knows both its neighbors, supports O(1) removal from anywhere and O(1) re-insertion at the front — exactly what's needed to move a just-accessed item to the 'most recent' end without scanning the list.

Why does a linked list have worse cache locality than an array, even though both are O(n) to traverse?

Array elements sit in one contiguous block of memory, so reading them sequentially is cache-friendly — the CPU can prefetch ahead. Linked list nodes are typically scattered across separately-allocated heap memory, so following next pointers jumps unpredictably around memory, causing more cache misses despite the same Big-O traversal cost.

What memory overhead does a linked list carry per element compared to a plain array of the same values?

Each node needs at least one pointer (next, plus prev for doubly linked), on top of the value itself, and each node is typically its own separate heap allocation with its own allocator bookkeeping overhead — whereas an array stores values back-to-back with no per-element pointer cost.

What is a circular doubly linked list, and where is it used?

A doubly linked list where the last node's next points to the first node and the first node's prev points to the last, forming a loop traversable in either direction. It shows up in things like looping playlists and in some LRU cache implementations, where wrapping around without special-casing the ends simplifies the logic.

What happens if a traversal loop's condition is `while (node.next)` instead of `while (node)`?

The loop body runs for every node except the last one — it stops as soon as node.next is null, meaning the final node is checked as node but never processed as node.next inside the loop, so it gets skipped even though no null-pointer error occurs.

Scenario: you're designing an LRU cache needing O(1) `get` and O(1) `put`. Why is a hash map or array alone insufficient?

A hash map alone gives O(1) lookup but no way to track order of recency or cheaply evict the least-recently-used item without scanning. An array can track order but costs O(n) to move an accessed item to the front or to remove an arbitrary item. Combining a hash map (for O(1) key lookup) with a doubly linked list (for O(1) reordering and eviction at either end) gives both properties at once.

What's the time complexity of accessing the head, the tail, and an arbitrary middle element of a singly linked list with only a head pointer?

Head: O(1), since it's directly referenced. Tail: O(n), since you must walk the whole list without a separate tail pointer. Middle: O(n), since reaching any position requires following next pointers from the head.