Linked Lists

A Linked List is a linear data structure where elements are stored in nodes. Each node contains data and a reference (pointer) to the next node in the sequence.

Node Structure

class Node {
  constructor(data) {
    this.data = data;  // The value
    this.next = null;  // Pointer to next node
  }
}

Arrays vs Linked Lists

Implementation

Singly Linked List

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

  // Insert at head - O(1)
  insertAtHead(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // Insert at tail - O(n)
  insertAtTail(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }

  // Delete at head - O(1)
  deleteAtHead() {
    if (!this.head) return null;
    const data = this.head.data;
    this.head = this.head.next;
    this.size--;
    return data;
  }

  // Search - O(n)
  search(data) {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.data === data) return index;
      current = current.next;
      index++;
    }
    return -1;
  }

  // Print list
  print() {
    let current = this.head;
    const elements = [];
    while (current) {
      elements.push(current.data);
      current = current.next;
    }
    console.log(elements.join(' → ') + ' → NULL');
  }
}

// Usage
const list = new LinkedList();
list.insertAtHead(42);
list.insertAtHead(25);
list.insertAtHead(10);
list.print(); // 10 → 25 → 42 → NULL

Types of Linked Lists

1. Singly Linked List

Each node points to the next node only.

[10|→] → [25|→] → [42|→] → NULL

2. Doubly Linked List

Each node points to both previous and next nodes.

NULL ← [←|10|→] ⟷ [←|25|→] ⟷ [←|42|→] → NULL

class DoublyNode {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

3. Circular Linked List

The last node points back to the first node.

[10|→] → [25|→] → [42|→] ─┐
  ↑                        │
  └────────────────────────┘

Common Operations

*With tail pointer

Classic Problem: Reverse a Linked List

function reverse(head) {
  let prev = null;
  let current = head;

  while (current) {
    const next = current.next; // Save next
    current.next = prev;       // Reverse pointer
    prev = current;            // Move prev forward
    current = next;            // Move current forward
  }

  return prev; // New head
}

When to Use Linked Lists

• Frequent insertions/deletions at the beginning
• Unknown or variable size
• Implementing stacks and queues
• When you don't need random access

• Random access patterns
• Small data sets (array overhead is less)
• Cache-sensitive applications

What's Next?

Next, we'll explore Trees — hierarchical data structures that extend the concept of linked nodes into branching structures, perfect for representing hierarchies and enabling fast searching.