Linked Lists

What is a Linked List?

A linked list is a linear data structure where elements (called nodes) are not stored in contiguous memory locations. Instead, each node contains data and a reference (or pointer) to the next node in the sequence. This structure allows for efficient insertion and deletion operations.

Unlike arrays, linked lists don't require shifting elements when inserting or deleting, making them ideal for scenarios where frequent modifications are needed.

Types of Linked Lists

Singly Linked List Implementation

Node Class

// Node class represents each element in the list
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

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

  // Get the size of the list - O(1)
  getSize() {
    return this.size;
  }

  // Check if list is empty - O(1)
  isEmpty() {
    return this.size === 0;
  }
}

Insert at Beginning - O(1)

insertAtBeginning(data) {
  const newNode = new Node(data);
  
  // Point new node to current head
  newNode.next = this.head;
  
  // Update head to new node
  this.head = newNode;
  
  this.size++;
}

// Usage
const list = new LinkedList();
list.insertAtBeginning(3);  // List: 3
list.insertAtBeginning(2);  // List: 2 → 3
list.insertAtBeginning(1);  // List: 1 → 2 → 3

Insert at End - O(n)

insertAtEnd(data) {
  const newNode = new Node(data);
  
  // If list is empty, new node becomes head
  if (this.isEmpty()) {
    this.head = newNode;
  } else {
    // Traverse to the end
    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
    // Attach new node at the end
    current.next = newNode;
  }
  
  this.size++;
}

// Note: Can optimize to O(1) by maintaining a tail pointer

Insert at Position - O(n)

insertAt(data, index) {
  if (index < 0 || index > this.size) {
    throw new Error('Invalid index');
  }
  
  // Insert at beginning
  if (index === 0) {
    this.insertAtBeginning(data);
    return;
  }
  
  const newNode = new Node(data);
  let current = this.head;
  
  // Traverse to position before insertion point
  for (let i = 0; i < index - 1; i++) {
    current = current.next;
  }
  
  // Insert new node
  newNode.next = current.next;
  current.next = newNode;
  
  this.size++;
}

Delete from Beginning - O(1)

deleteFromBeginning() {
  if (this.isEmpty()) {
    throw new Error('List is empty');
  }
  
  // Move head to next node
  const deletedData = this.head.data;
  this.head = this.head.next;
  
  this.size--;
  return deletedData;
}

Delete from End - O(n)

deleteFromEnd() {
  if (this.isEmpty()) {
    throw new Error('List is empty');
  }
  
  // If only one node
  if (this.head.next === null) {
    const deletedData = this.head.data;
    this.head = null;
    this.size--;
    return deletedData;
  }
  
  // Traverse to second-to-last node
  let current = this.head;
  while (current.next.next !== null) {
    current = current.next;
  }
  
  const deletedData = current.next.data;
  current.next = null;
  
  this.size--;
  return deletedData;
}

Search - O(n)

search(data) {
  let current = this.head;
  let index = 0;
  
  while (current !== null) {
    if (current.data === data) {
      return index;
    }
    current = current.next;
    index++;
  }
  
  return -1;  // Not found
}

contains(data) {
  return this.search(data) !== -1;
}

Display/Print List

print() {
  if (this.isEmpty()) {
    console.log('List is empty');
    return;
  }
  
  const values = [];
  let current = this.head;
  
  while (current !== null) {
    values.push(current.data);
    current = current.next;
  }
  
  console.log(values.join(' → '));
}

Doubly Linked List Implementation

// Node for doubly linked list
class DoublyNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

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

  // Insert at beginning - O(1)
  insertAtBeginning(data) {
    const newNode = new DoublyNode(data);
    
    if (this.isEmpty()) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    
    this.size++;
  }

  // Insert at end - O(1) with tail pointer!
  insertAtEnd(data) {
    const newNode = new DoublyNode(data);
    
    if (this.isEmpty()) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    
    this.size++;
  }

  // Delete from beginning - O(1)
  deleteFromBeginning() {
    if (this.isEmpty()) {
      throw new Error('List is empty');
    }
    
    const deletedData = this.head.data;
    
    if (this.head === this.tail) {
      this.head = this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }
    
    this.size--;
    return deletedData;
  }

  // Delete from end - O(1) with tail pointer!
  deleteFromEnd() {
    if (this.isEmpty()) {
      throw new Error('List is empty');
    }
    
    const deletedData = this.tail.data;
    
    if (this.head === this.tail) {
      this.head = this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }
    
    this.size--;
    return deletedData;
  }

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

Common Linked List Problems

1. Reverse a Linked List

function reverseList(head) {
  let prev = null;
  let current = head;
  
  while (current !== null) {
    // Save next node
    const nextNode = current.next;
    
    // Reverse the link
    current.next = prev;
    
    // Move pointers forward
    prev = current;
    current = nextNode;
  }
  
  return prev;  // New head
}

// Example: 1 → 2 → 3 → null becomes 3 → 2 → 1 → null

2. Detect Cycle (Floyd's Cycle Detection)

function hasCycle(head) {
  let slow = head;
  let fast = head;
  
  while (fast !== null && fast.next !== null) {
    slow = slow.next;        // Move 1 step
    fast = fast.next.next;   // Move 2 steps
    
    if (slow === fast) {
      return true;  // Cycle detected
    }
  }
  
  return false;  // No cycle
}

// If there's a cycle, fast will eventually meet slow

3. Find Middle Element

function findMiddle(head) {
  let slow = head;
  let fast = head;
  
  while (fast !== null && fast.next !== null) {
    slow = slow.next;        // Move 1 step
    fast = fast.next.next;   // Move 2 steps
  }
  
  return slow;  // Slow will be at middle
}

// When fast reaches end, slow will be at middle

4. Merge Two Sorted Lists

function mergeSortedLists(l1, l2) {
  const dummy = new Node(0);
  let current = dummy;
  
  while (l1 !== null && l2 !== null) {
    if (l1.data < l2.data) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }
  
  // Attach remaining nodes
  current.next = l1 !== null ? l1 : l2;
  
  return dummy.next;
}

5. Remove Nth Node from End

function removeNthFromEnd(head, n) {
  const dummy = new Node(0);
  dummy.next = head;
  
  let first = dummy;
  let second = dummy;
  
  // Move first n+1 steps ahead
  for (let i = 0; i <= n; i++) {
    first = first.next;
  }
  
  // Move both until first reaches end
  while (first !== null) {
    first = first.next;
    second = second.next;
  }
  
  // Remove the nth node
  second.next = second.next.next;
  
  return dummy.next;
}

Time Complexity Summary