Linked Lists - Complete Guide

Linked lists are fundamental data structures that store elements in nodes connected by pointers. This guide covers linked list operations and common problems.

What is a Linked List? #

A linked list is a linear data structure where elements are stored in nodes. Each node contains:

  • Data - The value
  • Next - Pointer to the next node

Types of Linked Lists #

Singly Linked List #

Each node points to the next node:

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

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

Doubly Linked List #

Each node points to both next and previous:

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

Circular Linked List #

Last node points back to first:

// Last node's next points to head

Basic Operations #

Insert at Beginning #

insertAtHead(data) {
  const newNode = new Node(data);
  newNode.next = this.head;
  this.head = newNode;
  this.size++;
}

// Usage
const list = new LinkedList();
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
// List: 1 -> 2 -> 3

Time: O(1)

Insert at End #

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++;
}

Time: O(n)

Insert at Position #

insertAt(data, index) {
  if (index < 0 || index > this.size) {
    return false;
  }

  if (index === 0) {
    this.insertAtHead(data);
    return true;
  }

  const newNode = new Node(data);
  let current = this.head;

  for (let i = 0; i < index - 1; i++) {
    current = current.next;
  }

  newNode.next = current.next;
  current.next = newNode;
  this.size++;

  return true;
}

Time: O(n)

Delete Node #

deleteAtHead() {
  if (!this.head) return null;

  const data = this.head.data;
  this.head = this.head.next;
  this.size--;

  return data;
}

deleteAtTail() {
  if (!this.head) return null;

  if (!this.head.next) {
    const data = this.head.data;
    this.head = null;
    this.size--;
    return data;
  }

  let current = this.head;
  while (current.next.next) {
    current = current.next;
  }

  const data = current.next.data;
  current.next = null;
  this.size--;

  return data;
}

deleteAt(index) {
  if (index < 0 || index >= this.size) {
    return null;
  }

  if (index === 0) {
    return this.deleteAtHead();
  }

  let current = this.head;
  for (let i = 0; i < index - 1; i++) {
    current = current.next;
  }

  const data = current.next.data;
  current.next = current.next.next;
  this.size--;

  return data;
}
search(data) {
  let current = this.head;
  let index = 0;

  while (current) {
    if (current.data === data) {
      return index;
    }
    current = current.next;
    index++;
  }

  return -1;
}

Time: O(n)

print() {
  const values = [];
  let current = this.head;

  while (current) {
    values.push(current.data);
    current = current.next;
  }

  console.log(values.join(' -> '));
}

Two Pointer Techniques #

Fast and Slow Pointers #

// Detect cycle
function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

// Find middle node
function findMiddle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

// Find cycle start
function detectCycle(head) {
  let slow = head;
  let fast = head;

  // Detect cycle
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      // Find start
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }

  return null;
}

Common Linked List Problems #

Reverse Linked List #

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

  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  return prev;
}

// Recursive
function reverseListRecursive(head) {
  if (!head || !head.next) {
    return head;
  }

  const newHead = reverseListRecursive(head.next);
  head.next.next = head;
  head.next = null;

  return newHead;
}

Time: O(n), Space: O(1)

Merge Two Sorted Lists #

function mergeTwoLists(l1, l2) {
  const dummy = new Node(0);
  let current = dummy;

  while (l1 && l2) {
    if (l1.data <= l2.data) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }

  current.next = l1 || l2;

  return dummy.next;
}

Time: O(n + m), Space: O(1)

Remove Nth Node From End #

function removeNthFromEnd(head, n) {
  const dummy = new Node(0);
  dummy.next = head;

  let fast = dummy;
  let slow = dummy;

  // Move fast n+1 steps ahead
  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }

  // Move both until fast reaches end
  while (fast) {
    fast = fast.next;
    slow = slow.next;
  }

  // Remove node
  slow.next = slow.next.next;

  return dummy.next;
}

Time: O(n), Space: O(1)

Palindrome Linked List #

function isPalindrome(head) {
  if (!head || !head.next) return true;

  // Find middle
  let slow = head;
  let fast = head;

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Reverse second half
  let secondHalf = reverseList(slow.next);
  let firstHalf = head;

  // Compare
  while (secondHalf) {
    if (firstHalf.data !== secondHalf.data) {
      return false;
    }
    firstHalf = firstHalf.next;
    secondHalf = secondHalf.next;
  }

  return true;
}

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

  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  return prev;
}

Time: O(n), Space: O(1)

Intersection of Two Linked Lists #

function getIntersectionNode(headA, headB) {
  let a = headA;
  let b = headB;

  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }

  return a;
}

Time: O(m + n), Space: O(1)

Remove Duplicates from Sorted List #

function deleteDuplicates(head) {
  let current = head;

  while (current && current.next) {
    if (current.data === current.next.data) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }

  return head;
}

Time: O(n), Space: O(1)

Add Two Numbers #

function addTwoNumbers(l1, l2) {
  const dummy = new Node(0);
  let current = dummy;
  let carry = 0;

  while (l1 || l2 || carry) {
    const sum = (l1?.data || 0) + (l2?.data || 0) + carry;
    carry = Math.floor(sum / 10);

    current.next = new Node(sum % 10);
    current = current.next;

    l1 = l1?.next;
    l2 = l2?.next;
  }

  return dummy.next;
}

Time: O(max(m, n)), Space: O(max(m, n))

Reorder List #

function reorderList(head) {
  if (!head || !head.next) return;

  // Find middle
  let slow = head;
  let fast = head;

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Reverse second half
  let secondHalf = reverseList(slow.next);
  slow.next = null;

  // Merge lists
  let first = head;
  let second = secondHalf;

  while (second) {
    const temp1 = first.next;
    const temp2 = second.next;

    first.next = second;
    second.next = temp1;

    first = temp1;
    second = temp2;
  }
}

Time: O(n), Space: O(1)

Sort List #

function sortList(head) {
  if (!head || !head.next) return head;

  // Find middle
  let slow = head;
  let fast = head;
  let prev = null;

  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }

  prev.next = null;

  // Sort halves
  const left = sortList(head);
  const right = sortList(slow);

  // Merge
  return merge(left, right);
}

function merge(l1, l2) {
  const dummy = new Node(0);
  let current = dummy;

  while (l1 && l2) {
    if (l1.data < l2.data) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }

  current.next = l1 || l2;
  return dummy.next;
}

Time: O(n log n), Space: O(log n)

Rotate List #

function rotateRight(head, k) {
  if (!head || !head.next || k === 0) return head;

  // Find length and connect to make circular
  let length = 1;
  let tail = head;

  while (tail.next) {
    tail = tail.next;
    length++;
  }

  tail.next = head;  // Make circular

  // Find new tail
  k = k % length;
  let stepsToNewTail = length - k;

  let newTail = head;
  for (let i = 1; i < stepsToNewTail; i++) {
    newTail = newTail.next;
  }

  const newHead = newTail.next;
  newTail.next = null;

  return newHead;
}

Time: O(n), Space: O(1)

Partition List #

function partition(head, x) {
  const lessDummy = new Node(0);
  const greaterDummy = new Node(0);

  let less = lessDummy;
  let greater = greaterDummy;
  let current = head;

  while (current) {
    if (current.data < x) {
      less.next = current;
      less = less.next;
    } else {
      greater.next = current;
      greater = greater.next;
    }
    current = current.next;
  }

  greater.next = null;
  less.next = greaterDummy.next;

  return lessDummy.next;
}

Time: O(n), Space: O(1)

Doubly Linked List Operations #

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

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

  insertAtHead(data) {
    const newNode = new DoublyNode(data);

    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
  }

  insertAtTail(data) {
    const newNode = new DoublyNode(data);

    if (!this.tail) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

  delete(node) {
    if (node.prev) {
      node.prev.next = node.next;
    } else {
      this.head = node.next;
    }

    if (node.next) {
      node.next.prev = node.prev;
    } else {
      this.tail = node.prev;
    }
  }
}

Linked List vs Array #

OperationLinked ListArray
AccessO(n)O(1)
Insert at startO(1)O(n)
Insert at endO(n) or O(1)*O(1) amortized
Delete at startO(1)O(n)
SearchO(n)O(n)
MemoryMore (pointers)Less

*O(1) if tail pointer is maintained

When to Use Linked Lists #

Use linked lists when:

  • Frequent insertions/deletions at beginning
  • Don’t need random access
  • Size changes frequently
  • Implementing stacks, queues, or graphs

Use arrays when:

  • Need random access
  • Memory is limited
  • Frequent access by index
  • Size is mostly fixed

Common Patterns #

  1. Dummy node - Simplifies edge cases
  2. Two pointers - Fast/slow for cycle detection, middle finding
  3. Reverse - For palindrome checking, reordering
  4. Runner technique - Slow and fast pointers
  5. Recursion - For reversal, merging

Linked lists are fundamental for understanding pointers and dynamic memory. Master these operations and patterns to solve any linked list problem.

Previous Tree Traversal Algorithms - Complete Guide LRU Cache - Complete Implementation Guide Next