Skip to content

Linked Lists Deep Dive

Implement singly, doubly, and circular linked lists; master pointer manipulation and cycle detection.

What you'll learn

  • Singly, doubly, and circular linked list variants
  • Pointer manipulation: insert, delete, reverse
  • Floyd's cycle detection algorithm
  • Merge sort on linked lists

Concept

Linked Lists Deep Dive

A linked list stores elements in nodes, each pointing to the next. Unlike arrays, linked lists do not store elements contiguously, so insertion and deletion at a known position is O(1) - you just relink pointers. The cost is O(n) random access.

Variants

Singly linked: each node has a next pointer. One-directional traversal. Doubly linked: each node has next and prev. Allows backward traversal and O(1) deletion given a node reference. Circular: the last node points back to the head. Useful for round-robin scheduling.

Pointer Manipulation

The key skill is drawing the pointers before and after. To insert node B after A: B.next = A.next; A.next = B. Order matters - if you set A.next = B first, you lose the reference to the old next. To reverse a list, maintain three pointers (prev, curr, next) and relink at each step.

Cycle Detection

Floyd's algorithm uses two pointers: a slow pointer (1 step) and a fast pointer (2 steps). If there is a cycle, they will meet. If the fast pointer reaches null, there is no cycle. This uses O(1) space.

Merge Sort on Lists

Merge sort is the natural sorting algorithm for linked lists: split at the midpoint (slow/fast pointer), recursively sort each half, then merge. It is O(n log n) with O(1) extra space.

Example

              class Node { constructor(val) { this.val = val; this.next = null; } }
function fromArray(arr) {
  const dummy = new Node(0); let tail = dummy;
  for (const v of arr) { tail.next = new Node(v); tail = tail.next; }
  return dummy.next;
}
function reverse(head) {
  let prev = null, curr = head;
  while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; }
  return prev;
}
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
function toArray(head) { const r = []; let c = head; while (c) { r.push(c.val); c = c.next; } return r; }
const list = fromArray([1, 2, 3, 4, 5]);
console.log('Original:', toArray(list));
console.log('Reversed:', toArray(reverse(list)));
            

reverse walks the list with three pointers, flipping each next to point backward. hasCycle uses Floyd tortoise-and-hare: if they meet, a cycle exists.

Try it

  • JSON Formatter

    Linked lists serialize to JSON arrays - see the structural difference between linked and contiguous storage.

Common mistakes

The mistake

Losing the rest of the list by breaking a pointer before saving it.

The fix

Always save the next pointer before overwriting. temp = curr.next; curr.next = newNext.

The mistake

Forgetting to handle edge cases: empty list, single node, two nodes.

The fix

Reverse of an empty list is empty. Reverse of a single node is itself. Test these explicitly.

Look up unfamiliar terms

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors