Linked Lists Explained

Introduction

A linked list stores a sequence of elements the same way an array does, but instead of sitting in one contiguous block of memory, each element (a "node") holds a reference to the next one. That single structural difference gives linked lists a completely different set of trade-offs from arrays — and a completely different set of interview questions.

Anatomy of a Singly Linked List

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

const list = new ListNode(1, new ListNode(2, new ListNode(3)));
// 1 -> 2 -> 3 -> null

There is no single block of memory holding "the list" — just a chain of independent node objects, each pointing to the next, ending in null.

Basic Operations

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

  prepend(value) {
    this.head = new ListNode(value, this.head); // O(1)
  }

  append(value) {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = node;
      return;
    }
    let current = this.head;
    while (current.next) current = current.next; // O(n)
    current.next = node;
  }

  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null; // O(n)
  }

  delete(value) {
    if (!this.head) return;
    if (this.head.value === value) {
      this.head = this.head.next;
      return;
    }
    let current = this.head;
    while (current.next && current.next.value !== value) {
      current = current.next;
    }
    if (current.next) current.next = current.next.next; // O(n)
  }
}

Prepending is O(1) because it only touches the head reference; appending, finding, and deleting a value are all O(n) in the worst case, since they may require walking the entire list.

Arrays vs Linked Lists

Operation                | Array        | Linked List
--------------------------|--------------|-------------
Access by index           | O(1)         | O(n)
Insert/delete at start     | O(n)         | O(1)
Insert/delete at end       | O(1)*        | O(n) (O(1) with a tail pointer)
Insert/delete in middle    | O(n)         | O(n) to find + O(1) to link
Memory overhead            | Low          | Higher (extra pointer per node)

* amortized, for dynamic arrays

Linked lists win specifically at insertion and deletion near the front, and lose specifically at random access — which is why they show up in problems explicitly designed around inserting, removing, or reordering nodes rather than looking things up by position.

Reversing a Linked List

One of the most common linked list interview questions, solved with three pointers tracking the current node, the previous node, and a temporary reference to the next node:

function reverseList(head) {
  let prev = null;
  let current = head;

  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  return prev; // new head
}

Trace through a small example (1 -> 2 -> 3) by hand: at each step, current.next is redirected backward to prev, and all three pointers shift forward by one node, until current becomes null and prev holds the new head.

Detecting a Cycle: Floyd's Algorithm

If a "linked list" accidentally (or intentionally, in some data corruption or interview scenario) has a node pointing back to an earlier node, naive traversal loops forever. Floyd's algorithm detects this using 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; // pointers met inside a cycle
  }

  return false; // fast reached the end, no cycle
}

If there is a cycle, the faster pointer will eventually "lap" the slower one and they will point to the same node; if there is no cycle, the faster pointer simply reaches the end (null) first. This is commonly nicknamed the "tortoise and hare" algorithm, and it runs in O(n) time using only O(1) extra space.

Finding the Middle Node in One Pass

The same two-speed pointer idea finds the middle node without first counting the list's length:

function findMiddle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow; // middle node (or the second of two middles for even-length lists)
}

Doubly Linked Lists

A doubly linked list adds a prev reference to each node, enabling backward traversal at the cost of extra memory:

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

This structure underlies things like browser history (back/forward navigation) and many implementations of LRU caches, where you frequently need to remove a node from the middle of the list in O(1) time once you already have a reference to it.

Best Practices

• Always handle the empty list (head === null) and single-node list cases explicitly — they are the most common source of edge-case bugs.
• Draw the list out on paper (or a whiteboard) before writing pointer-manipulation code; linked list bugs are almost always about pointer order.
• Use a "dummy head" node in operations like merging or removing elements to avoid special-casing the real head separately.
• Keep a tail pointer if your list frequently appends, turning an O(n) append into O(1).

Common Mistakes to Avoid

• Losing a reference to the rest of the list by reassigning .next before saving it in a temporary variable, especially during reversal.
• Forgetting to update the head reference when the operation happens to affect the very first node.
• Introducing an accidental cycle by pointing a node's .next back to an earlier node during a bug in list manipulation code.
• Assuming a list has at least two nodes when writing traversal logic, causing crashes on empty or single-node lists.

Finding the Middle Node in One Pass

A classic building block for many linked list problems — like checking if a list is a palindrome, or splitting a list in half — is finding the middle node without knowing the list's length ahead of time. The slow/fast pointer technique solves this in a single pass:

function findMiddle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow; // slow is now at the middle (or the second middle, for even length)
}

The insight is that fast moves twice as quickly as slow, so by the time fast reaches the end of the list, slow has covered exactly half the distance — arriving precisely at the middle without ever needing to count the list's total length first with a separate pass. This same slow/fast pointer setup, with a slightly different stopping condition, is also exactly how you detect a cycle in a linked list (Floyd's algorithm): if the list has a cycle, the fast pointer eventually laps the slow pointer and they meet at the same node; if the list has no cycle, the fast pointer simply reaches the end. Recognizing that "middle-finding" and "cycle detection" are really the same underlying two-pointer technique, applied with different exit conditions, is a good example of how a small number of core patterns cover a surprisingly large fraction of linked list problems.

Conclusion

Linked lists reward careful pointer bookkeeping more than clever algorithms — most of the classic problems (reversal, cycle detection, merging) come down to tracking a small number of references correctly as you walk through the chain. Practice tracing through examples by hand, and the two-pointer techniques used throughout this guide will start to feel like natural tools rather than memorized tricks.