Tech Blog

What is a Linked List?

A linked list is a linear data structure where each element (called a node) contains a value and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not store elements contiguously in memory, which makes insertion and deletion operations O(1) when the node is known.

Singly vs Doubly Linked Lists

Singly linked list: each node points only to its successor.

// Node structure
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

Doubly linked list: each node points to both its predecessor and successor, enabling backward traversal.

// Doubly node
class DNode {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

Core Operations

• Insert at head – O(1)
• Insert at tail – O(n) for singly, O(1) if tail reference is kept.
• Delete a node – O(1) if previous node is known.
• Search – O(n)

JavaScript Implementation (Singly)

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

  // Insert at the beginning
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  // Insert at the end
  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      let cur = this.head;
      while (cur.next) cur = cur.next;
      cur.next = node;
    }
    this.size++;
  }

  // Remove first occurrence of value
  remove(value) {
    if (!this.head) return;
    if (this.head.value === value) {
      this.head = this.head.next;
      this.size--;
      return;
    }
    let prev = this.head;
    let cur = this.head.next;
    while (cur && cur.value !== value) {
      prev = cur;
      cur = cur.next;
    }
    if (cur) {
      prev.next = cur.next;
      this.size--;
    }
  }

  // Convert to array for easy viewing
  toArray() {
    const arr = [];
    let cur = this.head;
    while (cur) {
      arr.push(cur.value);
      cur = cur.next;
    }
    return arr;
  }
}

// Demo
const list = new LinkedList();
list.append(10);
list.prepend(5);
list.append(15);
console.log(list.toArray()); // [5,10,15]
list.remove(10);
console.log(list.toArray()); // [5,15]

Interactive Visualization