sko.kr

Algorithms - 10. Linked List

algorithmsdata-structureslinked-listpointersdynamic-memory
By sko•10/7/2025•7 min read

When to use Linked List

Use Linked List when you need dynamic size with efficient insertion/deletion at known positions. While arrays excel at random access, linked lists shine for:

  • Frequent insertions/deletions at front (classic use case)
  • Implementing stacks and queues (with O(1) operations)
  • Undo functionality (maintaining operation history)
  • Music playlists (next/previous navigation)
  • Browser history (forward/backward navigation)
  • Any problem where you frequently add/remove elements and don't need random access

Example problem

Text Editor Undo System: You're building a text editor that needs to track every edit operation for unlimited undo/redo functionality.

  • User types "Hello" (5 operations)
  • User deletes "lo" (2 operations)
  • User types " World" (6 operations)
  • User wants to undo last 3 operations

Answer: A linked list perfectly maintains the operation sequence, allowing O(1) insertion of new operations and easy traversal backwards for undo operations. Unlike an array, we don't waste memory pre-allocating space we might not use.

Single most important insight

A linked list trades random access for the ability to insert/delete anywhere in O(1) time - and by using dummy nodes at boundaries, we eliminate all edge cases because there's always a node before and after our operation point.

Mental note: The linked list's genius lies in its pointer-based connections. Each node only knows about its immediate neighbor(s), creating a chain. This local knowledge means we can insert or remove nodes by just updating a few pointers - no shifting of elements needed. The dummy node pattern ensures we never deal with null head/tail, making every operation uniform.

Decision Framework

At every linked list operation, the decision is about pointer manipulation:

  • Insert: Update pointers to weave new node into the chain
  • Delete: Update pointers to bypass the target node
  • Traverse: Follow the chain one node at a time
  • Edge case elimination: Use dummy nodes to ensure uniform operations

Code

Singly Linked List with Dummy Node

// Each element in our list is a "node" with a value and pointer to next
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null; // Points to the next node in chain
  }
}

class LinkedList {
  constructor() {
    // Dummy head acts like a permanent "start" marker
    this.dummyHead = new ListNode("START");
    this.tail = this.dummyHead; // Tail tracks the last node
  }

  // push: Add to the end (like array.push)
  push(value) {
    const newNode = new ListNode(value);

    // DECISION FRAMEWORK: Simply attach to tail
    this.tail.next = newNode; // Current last node points to new node
    this.tail = newNode; // Update tail to be the new last node
  }

  // pop: Remove from the end (like array.pop)
  pop() {
    // DECISION FRAMEWORK: Check if list is empty
    if (this.dummyHead.next === null) {
      return undefined;
    }

    // Find the second-to-last node
    let current = this.dummyHead;
    while (current.next !== this.tail) {
      current = current.next;
    }

    // Save value to return
    const poppedValue = this.tail.value;

    // Remove last node
    current.next = null;
    this.tail = current;

    return poppedValue;
  }

  // unshift: Add to the front (like array.unshift)
  unshift(value) {
    const newNode = new ListNode(value);

    // DECISION FRAMEWORK: Insert right after dummy
    const oldFirst = this.dummyHead.next;
    newNode.next = oldFirst; // New node points to old first
    this.dummyHead.next = newNode; // Dummy points to new node

    // If list was empty, update tail
    if (this.tail === this.dummyHead) {
      this.tail = newNode;
    }
  }

  // shift: Remove from the front (like array.shift)
  shift() {
    // DECISION FRAMEWORK: Check if list is empty
    if (this.dummyHead.next === null) {
      return undefined;
    }

    const firstNode = this.dummyHead.next;
    const shiftedValue = firstNode.value;

    // Bypass first node
    this.dummyHead.next = firstNode.next;

    // If we removed the only node, reset tail
    if (firstNode === this.tail) {
      this.tail = this.dummyHead;
    }

    return shiftedValue;
  }

  // Helper: See what's in the list
  display() {
    const items = [];
    let current = this.dummyHead.next; // Skip dummy

    while (current !== null) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" → ");
  }
}

// Example: Managing a todo list
const todos = new LinkedList();

// Add tasks to the end
todos.push("Buy milk");
todos.push("Write code");
todos.push("Exercise");
console.log(todos.display()); // Buy milk → Write code → Exercise

// Add urgent task to front
todos.unshift("Call mom");
console.log(todos.display()); // Call mom → Buy milk → Write code → Exercise

// Complete first task
const completed = todos.shift();
console.log(`Completed: ${completed}`); // Completed: Call mom
console.log(todos.display()); // Buy milk → Write code → Exercise

// Remove last task
const removed = todos.pop();
console.log(`Removed: ${removed}`); // Removed: Exercise
console.log(todos.display()); // Buy milk → Write code

Doubly Linked List with Dual Dummy Nodes

// Each node has pointers to both next AND previous nodes
class DoublyListNode {
  constructor(value) {
    this.value = value;
    this.next = null; // Points forward
    this.prev = null; // Points backward
  }
}

class DoublyLinkedList {
  constructor() {
    // Two dummy nodes act as permanent "bookends"
    this.dummyHead = new DoublyListNode("START");
    this.dummyTail = new DoublyListNode("END");

    // Connect the bookends to each other
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }

  // push: Add to the end (like array.push)
  push(value) {
    const newNode = new DoublyListNode(value);

    // DECISION FRAMEWORK: Insert between last real node and dummyTail
    const lastNode = this.dummyTail.prev;

    // Wire up all 4 connections
    newNode.prev = lastNode; // New node points back to last
    newNode.next = this.dummyTail; // New node points forward to dummy tail
    lastNode.next = newNode; // Last node points forward to new
    this.dummyTail.prev = newNode; // Dummy tail points back to new

    return this; // For chaining
  }

  // pop: Remove from the end (like array.pop)
  pop() {
    // DECISION FRAMEWORK: Check if list is empty
    if (this.dummyHead.next === this.dummyTail) {
      return undefined;
    }

    const lastNode = this.dummyTail.prev;
    const secondToLast = lastNode.prev;
    const poppedValue = lastNode.value;

    // Bypass the last node
    secondToLast.next = this.dummyTail;
    this.dummyTail.prev = secondToLast;

    return poppedValue;
  }

  // unshift: Add to the front (like array.unshift)
  unshift(value) {
    const newNode = new DoublyListNode(value);

    // DECISION FRAMEWORK: Insert between dummyHead and first real node
    const firstNode = this.dummyHead.next;

    // Wire up all 4 connections
    newNode.prev = this.dummyHead; // New node points back to dummy head
    newNode.next = firstNode; // New node points forward to first
    this.dummyHead.next = newNode; // Dummy head points forward to new
    firstNode.prev = newNode; // First node points back to new

    return this; // For chaining
  }

  // shift: Remove from the front (like array.shift)
  shift() {
    // DECISION FRAMEWORK: Check if list is empty
    if (this.dummyHead.next === this.dummyTail) {
      return undefined;
    }

    const firstNode = this.dummyHead.next;
    const secondNode = firstNode.next;
    const shiftedValue = firstNode.value;

    // Bypass the first node
    this.dummyHead.next = secondNode;
    secondNode.prev = this.dummyHead;

    return shiftedValue;
  }

  // Helper: See what's in the list
  display() {
    const items = [];
    let current = this.dummyHead.next;

    while (current !== this.dummyTail) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" ⟷ ");
  }

  // Bonus: Navigate backwards
  displayReverse() {
    const items = [];
    let current = this.dummyTail.prev;

    while (current !== this.dummyHead) {
      items.push(current.value);
      current = current.prev;
    }

    return items.join(" ⟷ ");
  }
}

// Example: Music playlist with next/previous
const playlist = new DoublyLinkedList();

// Add songs
playlist.push("Song A");
playlist.push("Song B");
playlist.push("Song C");
console.log(playlist.display()); // Song A ⟷ Song B ⟷ Song C

// Add song to beginning
playlist.unshift("Intro Song");
console.log(playlist.display()); // Intro Song ⟷ Song A ⟷ Song B ⟷ Song C

// Play in reverse
console.log("Reverse:", playlist.displayReverse()); // Song C ⟷ Song B ⟷ Song A ⟷ Intro Song

// Skip first song
const skipped = playlist.shift();
console.log(`Skipped: ${skipped}`); // Skipped: Intro Song

// Remove last song
const removed = playlist.pop();
console.log(`Removed: ${removed}`); // Removed: Song C

console.log(playlist.display()); // Song A ⟷ Song B

Doubt buster

Common doubt: "Why use linked lists when arrays seem simpler? Arrays give us direct access to any element with an index!"

This is a fundamental question about choosing the right data structure. Let's examine the tradeoffs.

Why you might think arrays are always better

Consider these array advantages:

  • "Arrays give O(1) random access with indices"
  • "Arrays have better cache locality (elements stored contiguously)"
  • "No extra memory needed for pointers"
  • "Simpler mental model - just a continuous block"

Why this thinking misses crucial scenarios

Key realization: Arrays have a hidden cost for insertions and deletions!

Let's trace what happens when inserting in the middle of an array:

Array: [A, B, C, D, E]
Insert X at index 2:

Step 1: Make space by shifting everything right
[A, B, _, C, D, E]  // C moved to index 3
[A, B, _, _, D, E]  // D moved to index 4
[A, B, _, _, _, E]  // E moved to index 5

Step 2: Insert X
[A, B, X, C, D, E]

Total operations: n/2 shifts on average = O(n)

Concrete example: Performance comparison

Inserting 1000 elements at the front:

Array approach:

  • First insert: shift 0 elements
  • Second insert: shift 1 element
  • Third insert: shift 2 elements
  • ...
  • 1000th insert: shift 999 elements
  • Total shifts: 0 + 1 + 2 + ... + 999 = 499,500 operations!

Linked list approach:

  • Every insert: update 2 pointers
  • Total operations: 1000 × 2 = 2,000 operations

That's 250× fewer operations with a linked list!

When each structure shines

Use Arrays when:

  • You need random access (accessing arr[500] directly)
  • Data size is relatively fixed
  • You mostly read data
  • Cache performance matters

Use Linked Lists when:

  • Frequent insertions/deletions at known positions
  • Data size varies significantly
  • You only traverse sequentially
  • Memory is fragmented (linked lists can use scattered memory)

Why dummy nodes are genius

Without dummy nodes, every operation must check:

  • "Is this the first node?" (special case for head)
  • "Is this the last node?" (special case for tail)
  • "Is the list empty?" (null checks everywhere)

With dummy nodes:

  • There's always a node before your target (dummyHead)
  • There's always a node after your target (dummyTail in doubly-linked)
  • Empty list still has the dummy structure
  • Every operation uses the same pattern - no special cases!

The guarantee: Dummy nodes transform a data structure full of edge cases into one with uniform operations. This isn't just convenience - it's about writing bug-free code by eliminating the possibility of null pointer errors and special case handling.

← Back to Blog