← Index

Linear Structures

Linked List

A chain of nodes — cheap inserts anywhere, no random access.

What it is

A linked list is a chain of nodes, each holding a value and a pointer to the next node. There's no contiguous memory and no indexes — to reach the 50th element you have to walk through the first 49. What you gain: inserting or removing a node (once you're there) is O(1), no shifting required, because you're just relinking pointers.

Real-world examples

• A treasure hunt where each clue tells you where to find the next one — you can't jump to clue #7, you have to follow the chain from the start.
• A conga line: adding or removing a person only requires the people immediately next to them to reconnect hands, nobody else moves.

Where you've probably used this already

• React/Redux's fiber tree and undo histories are often linked-list-shaped under the hood for O(1) insert/remove.
• Implementing an LRU cache — a doubly linked list + a hash map is the textbook combo for O(1) get/put/evict.
• Debugging a 'Maximum call stack exceeded' from a deeply recursive traversal of a huge list — classic linked-list-recursion trap.

Complexity

Code

// Singly Linked List — a chain of nodes, each pointing to the next.
// No indexes, no contiguous memory. To reach node #50 you walk through 1-49 first.

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

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

  // Add to the end — O(1) because we keep a tail pointer
  append(value) {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
    return this;
  }

  // Add to the front — O(1), no shifting like an array would need
  prepend(value) {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
    this.length++;
    return this;
  }

  // Get value at index — O(n), must walk from head
  get(index) {
    if (index < 0 || index >= this.length) return null;
    let current = this.head;
    for (let i = 0; i < index; i++) current = current.next;
    return current.value;
  }

  // Remove the first node matching a value — O(n)
  remove(value) {
    if (!this.head) return false;
    if (this.head.value === value) {
      this.head = this.head.next;
      this.length--;
      return true;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.value === value) {
        current.next = current.next.next;
        this.length--;
        return true;
      }
      current = current.next;
    }
    return false;
  }

  toArray() {
    const out = [];
    let current = this.head;
    while (current) {
      out.push(current.value);
      current = current.next;
    }
    return out;
  }
}

// --- Example Usage ---
const list = new LinkedList();
list.append("a").append("b").append("c");
list.prepend("start");
console.log("List:", list.toArray()); // ["start","a","b","c"]

console.log("get(2):", list.get(2)); // "b"

list.remove("b");
console.log("After remove('b'):", list.toArray()); // ["start","a","c"]