Linked Lists for Complete Beginners

A linked list is like a chain of boxes. Each box (called a node) holds a value and a pointer to the next box. With a singly linked list, each box points forward. With a doubly linked list, each box points forward and backward. This makes inserting and removing in the middle efficient without shifting items like in arrays.

JavaScript Implementation


// Singly Linked List - OOP Implementation
class SLLNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  // O(1)
  isEmpty() { return this.length === 0; }

  // O(1) - insert at end
  push(value) {
    const node = new SLLNode(value);
    if (this.isEmpty()) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
    return this;
  }

  // O(1) - insert at start
  unshift(value) {
    const node = new SLLNode(value);
    if (this.isEmpty()) {
      this.head = this.tail = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
    this.length++;
    return this;
  }

  // O(n) - insert at index (0..length)
  insertAt(index, value) {
    if (index < 0 || index > this.length) throw new RangeError("Index out of range");
    if (index === 0) return this.unshift(value);
    if (index === this.length) return this.push(value);
    const node = new SLLNode(value);
    let prev = this.head;
    for (let i = 0; i < index - 1; i++) prev = prev.next;
    node.next = prev.next;
    prev.next = node;
    this.length++;
    return this;
  }

  // O(1) - remove from start
  shift() {
    if (this.isEmpty()) return undefined;
    const val = this.head.value;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) this.tail = null;
    return val;
  }

  // O(n) - remove from end
  pop() {
    if (this.isEmpty()) return undefined;
    if (this.length === 1) {
      const val = this.head.value;
      this.head = this.tail = null;
      this.length = 0;
      return val;
    }
    let prev = this.head;
    while (prev.next !== this.tail) prev = prev.next;
    const val = this.tail.value;
    prev.next = null;
    this.tail = prev;
    this.length--;
    return val;
  }

  // O(n) - remove at index
  removeAt(index) {
    if (index < 0 || index >= this.length) throw new RangeError("Index out of range");
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();
    let prev = this.head;
    for (let i = 0; i < index - 1; i++) prev = prev.next;
    const val = prev.next.value;
    prev.next = prev.next.next;
    this.length--;
    return val;
  }

  // O(n) - get node at index
  _getNode(index) {
    if (index < 0 || index >= this.length) return null;
    let cur = this.head;
    for (let i = 0; i < index; i++) cur = cur.next;
    return cur;
  }

  // O(n)
  get(index) {
    const node = this._getNode(index);
    return node ? node.value : undefined;
  }

  // O(n)
  set(index, value) {
    const node = this._getNode(index);
    if (!node) return false;
    node.value = value;
    return true;
  }

  // O(n) - returns first index or -1
  indexOf(value) {
    let cur = this.head, i = 0;
    while (cur) {
      if (cur.value === value) return i;
      cur = cur.next; i++;
    }
    return -1;
  }

  contains(value) { return this.indexOf(value) !== -1; } // O(n)

  // O(n)
  traverse(visit) {
    let cur = this.head;
    while (cur) {
      visit(cur.value);
      cur = cur.next;
    }
  }

  toArray() {
    const arr = [];
    this.traverse(v => arr.push(v));
    return arr;
  }

  // O(n) - reverse in place
  reverse() {
    let prev = null, cur = this.head;
    this.tail = this.head;
    while (cur) {
      const next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }
    this.head = prev;
    return this;
  }

  // O(1)
  clear() {
    this.head = this.tail = null;
    this.length = 0;
  }

  size() { return this.length; }
}

// Example usage:
const sll = new SinglyLinkedList();
sll.push(10).push(20).unshift(5); // [5,10,20]
sll.insertAt(1, 7);               // [5,7,10,20]
sll.removeAt(2);                  // removes 10
sll.reverse();                    // [20,7,5]
console.log(sll.toArray());

// Doubly Linked List - OOP Implementation
class DLLNode {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

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

  isEmpty() { return this.length === 0; }
  size() { return this.length; }

  // O(1)
  push(value) {
    const node = new DLLNode(value);
    if (this.isEmpty()) {
      this.head = this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
    return this;
  }

  // O(1)
  unshift(value) {
    const node = new DLLNode(value);
    if (this.isEmpty()) {
      this.head = this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
    this.length++;
    return this;
  }

  // O(1)
  shift() {
    if (this.isEmpty()) return undefined;
    const val = this.head.value;
    if (this.length === 1) {
      this.head = this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }
    this.length--;
    return val;
  }

  // O(1)
  pop() {
    if (this.isEmpty()) return undefined;
    const val = this.tail.value;
    if (this.length === 1) {
      this.head = this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }
    this.length--;
    return val;
  }

  // O(n) but can traverse from closer end
  _getNode(index) {
    if (index < 0 || index >= this.length) return null;
    let cur, i;
    if (index < this.length / 2) {
      cur = this.head; i = 0;
      while (i++ < index) cur = cur.next;
    } else {
      cur = this.tail; i = this.length - 1;
      while (i-- > index) cur = cur.prev;
    }
    return cur;
  }

  get(index) {
    const node = this._getNode(index);
    return node ? node.value : undefined;
  }

  set(index, value) {
    const node = this._getNode(index);
    if (!node) return false;
    node.value = value;
    return true;
  }

  // O(n)
  insertAt(index, value) {
    if (index < 0 || index > this.length) throw new RangeError("Index out of range");
    if (index === 0) return this.unshift(value);
    if (index === this.length) return this.push(value);

    const nextNode = this._getNode(index);
    const prevNode = nextNode.prev;
    const node = new DLLNode(value);

    node.prev = prevNode;
    node.next = nextNode;
    prevNode.next = node;
    nextNode.prev = node;

    this.length++;
    return this;
  }

  // O(n)
  removeAt(index) {
    if (index < 0 || index >= this.length) throw new RangeError("Index out of range");
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    const node = this._getNode(index);
    const val = node.value;
    node.prev.next = node.next;
    node.next.prev = node.prev;
    this.length--;
    return val;
  }

  indexOf(value) {
    let cur = this.head, i = 0;
    while (cur) {
      if (cur.value === value) return i;
      cur = cur.next; i++;
    }
    return -1;
  }
  contains(value) { return this.indexOf(value) !== -1; }

  traverseForward(visit) {
    let cur = this.head;
    while (cur) { visit(cur.value); cur = cur.next; }
  }

  traverseBackward(visit) {
    let cur = this.tail;
    while (cur) { visit(cur.value); cur = cur.prev; }
  }

  // O(n) - reverse by swapping next/prev
  reverse() {
    let cur = this.head;
    this.tail = this.head;
    while (cur) {
      const temp = cur.next;
      cur.next = cur.prev;
      cur.prev = temp;
      cur = temp;
    }
    // rebuild head from old tail
    let newHead = this.tail;
    cur = newHead;
    while (cur && cur.prev) cur = cur.prev;
    this.head = cur || newHead;
    return this;
  }

  clear() { this.head = this.tail = null; this.length = 0; }
}

// Example usage:
const dll = new DoublyLinkedList();
dll.push("A").push("B").push("C");   // A <-> B <-> C
dll.insertAt(1, "X");                // A <-> X <-> B <-> C
dll.removeAt(2);                     // remove B
dll.traverseBackward(v => console.log(v));

Complete Explanation of the Code

Nodes: SLLNode has value and next. DLLNode adds prev so we can move backward.
List state: each list tracks head, tail, and length. Empty means head = tail = null and length = 0.
Insertions: push appends in O(1); unshift prepends in O(1); insertAt walks to position and rewires pointers (O(n)).
Removals: shift removes the first node in O(1); pop is O(n) for singly (scan to node before tail) but O(1) for doubly; removeAt adjusts neighbors to bypass the target node.
Access/update: _getNode walks to an index. DLL chooses the closer end for fewer steps. get/set use that helper.
Search & traverse: indexOf/contains scan nodes. traverse runs a callback for each value; toArray collects values.
Reverse: SLL re-points each next backward in one pass. DLL swaps next/prev per node then rebuilds the new head from the old tail.
Cleanup: clear() drops references so the garbage collector can free nodes; size() returns the current count.
Examples: The sample lines show typical sequences of insert, remove, and traversal for both lists.

Performance Note: In a singly list, removing the last element (pop()) is O(n) because there is no backward link to the node before tail. In a doubly list, pop() is O(1). All random index operations remain O(n) because lists do not support constant-time direct indexing like arrays.

Standard Pseudocode


PROCEDURE SLL_INSERT_AT(index, value)
  IF index < 0 OR index > length THEN
    OUTPUT "Index out of range"
    RETURN
  END IF
  IF index = 0 THEN
    INITIALIZE node AS NEW NODE(value)
    SET node.next TO head
    SET head TO node
    IF length = 0 THEN
      SET tail TO node
    END IF
    INCREMENT length
    RETURN
  END IF
  IF index = length THEN
    INITIALIZE node AS NEW NODE(value)
    IF length = 0 THEN
      SET head TO node
      SET tail TO node
    ELSE
      SET tail.next TO node
      SET tail TO node
    END IF
    INCREMENT length
    RETURN
  END IF
  SET prev TO head
  FOR i FROM 0 TO index - 2 DO
    SET prev TO prev.next
  END FOR
  INITIALIZE node AS NEW NODE(value)
  SET node.next TO prev.next
  SET prev.next TO node
  INCREMENT length
END PROCEDURE

FUNCTION SLL_REMOVE_AT(index) RETURNS value
  IF index < 0 OR index ≥ length THEN
    OUTPUT "Index out of range"
    RETURN UNDEFINED
  END IF
  IF index = 0 THEN
    SET value TO head.value
    SET head TO head.next
    DECREMENT length
    IF length = 0 THEN
      SET tail TO NULL
    END IF
    RETURN value
  END IF
  IF index = length - 1 THEN
    IF length = 1 THEN
      SET value TO head.value
      SET head TO NULL
      SET tail TO NULL
      SET length TO 0
      RETURN value
    END IF
    SET prev TO head
    WHILE prev.next ≠ tail DO
      SET prev TO prev.next
    END WHILE
    SET value TO tail.value
    SET prev.next TO NULL
    SET tail TO prev
    DECREMENT length
    RETURN value
  END IF
  SET prev TO head
  FOR i FROM 0 TO index - 2 DO
    SET prev TO prev.next
  END FOR
  SET value TO prev.next.value
  SET prev.next TO prev.next.next
  DECREMENT length
  RETURN value
END FUNCTION

PROCEDURE SLL_REVERSE()
  SET prev TO NULL
  SET cur TO head
  SET tail TO head
  WHILE cur ≠ NULL DO
    SET next TO cur.next
    SET cur.next TO prev
    SET prev TO cur
    SET cur TO next
  END WHILE
  SET head TO prev
END PROCEDURE

PROCEDURE DLL_INSERT_AT(index, value)
  IF index < 0 OR index > length THEN
    OUTPUT "Index out of range"
    RETURN
  END IF
  IF index = 0 THEN
    INITIALIZE node AS NEW NODE(value)
    IF length = 0 THEN
      SET head TO node
      SET tail TO node
    ELSE
      SET node.next TO head
      SET head.prev TO node
      SET head TO node
    END IF
    INCREMENT length
    RETURN
  END IF
  IF index = length THEN
    INITIALIZE node AS NEW NODE(value)
    IF length = 0 THEN
      SET head TO node
      SET tail TO node
    ELSE
      SET node.prev TO tail
      SET tail.next TO node
      SET tail TO node
    END IF
    INCREMENT length
    RETURN
  END IF
  SET nextNode TO GET_NODE(index)
  SET prevNode TO nextNode.prev
  INITIALIZE node AS NEW NODE(value)
  SET node.prev TO prevNode
  SET node.next TO nextNode
  SET prevNode.next TO node
  SET nextNode.prev TO node
  INCREMENT length
END PROCEDURE

FUNCTION DLL_REMOVE_AT(index) RETURNS value
  IF index < 0 OR index ≥ length THEN
    OUTPUT "Index out of range"
    RETURN UNDEFINED
  END IF
  IF index = 0 THEN
    SET value TO head.value
    IF length = 1 THEN
      SET head TO NULL
      SET tail TO NULL
    ELSE
      SET head TO head.next
      SET head.prev TO NULL
    END IF
    DECREMENT length
    RETURN value
  END IF
  IF index = length - 1 THEN
    SET value TO tail.value
    IF length = 1 THEN
      SET head TO NULL
      SET tail TO NULL
    ELSE
      SET tail TO tail.prev
      SET tail.next TO NULL
    END IF
    DECREMENT length
    RETURN value
  END IF
  SET node TO GET_NODE(index)
  SET value TO node.value
  SET node.prev.next TO node.next
  SET node.next.prev TO node.prev
  DECREMENT length
  RETURN value
END FUNCTION

PROCEDURE DLL_REVERSE()
  SET cur TO head
  SET tail TO head
  WHILE cur ≠ NULL DO
    SET temp TO cur.next
    SET cur.next TO cur.prev
    SET cur.prev TO temp
    SET cur TO temp
  END WHILE
  SET newHead TO tail
  SET cur TO newHead
  WHILE cur ≠ NULL AND cur.prev ≠ NULL DO
    SET cur TO cur.prev
  END WHILE
  SET head TO cur
END PROCEDURE

Explanation of the Pseudocode

Bounds checks prevent illegal positions that would break the chain of nodes.
Insert at front/end mirrors unshift/push: adjust head/tail and neighbors, then update length.
Insert in middle walks to the node before the target index and rewires two links so the new node sits between them.
Remove at front/end updates head or tail; DLL can do tail removal without scanning because it has prev.
Remove in middle bypasses the target by reconnecting its neighbors; in SLL we must know the previous node.
Reverse (SLL) flips each next pointer in one pass and swaps which node is the head/tail.
Reverse (DLL) swaps each node’s next/prev, then walks back via prev to discover the new head.
Return values on removals match the JavaScript methods that give back the removed element.