Linked Lists in DSA: Master Single, Double & Circular Lists

This tutorial covers linked list operations, time complexities, and practical implementations with coding examples. Learn to reverse lists, detect cycles, and solve common interview problems.

Linked List Usage in Systems (2023)

Memory Management (50%)

LRU Caches (25%)

File Systems (15%)

Other (10%)

1. Linked List Fundamentals

Core Characteristics:

Node Structure: Value + Pointer to next node
Dynamic Size: Grows/shrinks at runtime
Non-contiguous Memory: Nodes scattered in memory

Time Complexities:

Operation	Singly LL	Doubly LL
Access	O(n)	O(n)
Insert Head	O(1)	O(1)
Insert Tail	O(n)*	O(1)
Delete Head	O(1)	O(1)

* O(1) with tail pointer

Node Implementation:


// Singly Linked List Node
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Doubly Linked List Node
class DoublyListNode {
  constructor(val, prev = null, next = null) {
    this.val = val;
    this.prev = prev;
    this.next = next;
  }
}

2. Essential Operations

Core Algorithms:

Reverse Linked List


function reverseList(head) {
  let prev = null;
  let curr = head;
  
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  
  return prev;
}

Cycle Detection


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

Common Patterns:

Fast & Slow Pointers: Middle node detection
Dummy Nodes: Simplify edge cases
Merge Intervals: Combine sorted lists
Two Pass: Find nth from end

3. Advanced Techniques

Complex Problem Solutions:

Merge K Sorted Lists


function mergeKLists(lists) {
  if (!lists.length) return null;
  
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      const l1 = lists[i];
      const l2 = i + 1 < lists.length ? lists[i + 1] : null;
      merged.push(mergeTwo(l1, l2));
    }
    lists = merged;
  }
  
  return lists[0];
}

function mergeTwo(l1, l2) {
  const dummy = new ListNode();
  let tail = dummy;
  
  while (l1 && l2) {
    if (l1.val < l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  
  tail.next = l1 || l2;
  return dummy.next;
}

LRU Cache Implementation


class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new DoublyListNode(0, 0);
    this.tail = new DoublyListNode(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this.remove(node);
    this.add(node);
    return node.value;
  }
  
  put(key, value) {
    if (this.map.has(key)) this.remove(this.map.get(key));
    const node = new DoublyListNode(key, value);
    this.add(node);
    this.map.set(key, node);
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev;
      this.remove(lru);
      this.map.delete(lru.key);
    }
  }
  
  add(node) {
    const next = this.head.next;
    this.head.next = node;
    node.prev = this.head;
    node.next = next;
    next.prev = node;
  }
  
  remove(node) {
    const prev = node.prev;
    const next = node.next;
    prev.next = next;
    next.prev = prev;
  }
}

Linked List Problem-Solving Cheat Sheet

Problem Type	Technique	Time Complexity
Reverse List	Iterative Pointers	O(n)
Find Middle	Fast & Slow Pointers	O(n)
Merge Two Lists	Dummy Node	O(n+m)
Detect Cycle	Floyd's Algorithm	O(n)

4. Specialized Linked Lists

Circular Linked List

Tail connects back to head


function isCircular(head) {
  if (!head) return false;
  let slow = head;
  let fast = head.next;
  
  while (fast && fast.next) {
    if (slow === fast) return true;
    slow = slow.next;
    fast = fast.next.next;
  }
  
  return false;
}

Skip List

Multi-level linked list for fast search


class SkipListNode {
  constructor(val, levels = 1) {
    this.val = val;
    this.next = new Array(levels).fill(null);
  }
}

Unrolled Linked List

Each node contains multiple elements


class UnrolledNode {
  constructor(capacity) {
    this.elements = new Array(capacity);
    this.next = null;
    this.size = 0;
  }
}

Linked List Problem-Solving Checklist

✓ Handle empty list and single node cases

✓ Manage pointers carefully during modifications

✓ Consider using dummy nodes for edge cases

✓ Verify cycle termination conditions

DSA Expert Insight: Linked lists appear in 25% of technical interviews. Mastering pointer manipulation and the fast/slow pointer technique can help solve most linked list problems efficiently.

0 Interaction

0 Views

0 Likes