Linked Lists

Interactive Visualization

Time Complexity

Key Points

• Each node has: data + pointer to next node
• No contiguous memory needed - nodes can be anywhere
• O(1) insert/delete if you have the node reference
• O(n) access - must traverse from head
• Types: singly linked, doubly linked, circular
• Trade-off: fast insert/delete vs slow random access

Code Examples

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

// Create a linked list: 1 → 2 → 3
const head = new ListNode(1)
head.next = new ListNode(2)
head.next.next = new ListNode(3)

// Traverse the list
let current = head
while (current !== null) {
  console.log(current.val)  // 1, 2, 3
  current = current.next
}

function insertAtHead(head, val) {
  const newNode = new ListNode(val)
  newNode.next = head
  return newNode  // New head
}

// Before: 1 → 2 → 3
// insertAtHead(head, 0)
// After: 0 → 1 → 2 → 3

// O(1) - just update pointers!
// Compare to array unshift which is O(n)

function insertAt(head, val, position) {
  const newNode = new ListNode(val)

  if (position === 0) {
    newNode.next = head
    return newNode
  }

  let current = head
  for (let i = 0; i < position - 1; i++) {
    if (!current) return head
    current = current.next
  }

  newNode.next = current.next
  current.next = newNode
  return head
}

// Must traverse to find position: O(n)
// But the actual insertion is O(1)

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

  while (current !== null) {
    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
}

// Before: 1 → 2 → 3 → null
// After:  null ← 1 ← 2 ← 3
// Return: 3 → 2 → 1 → null

// Classic interview question!

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  // They met - cycle exists!
    }
  }

  return false  // Fast reached end - no cycle
}

// Tortoise and Hare algorithm
// If there's a cycle, fast will "lap" slow
// O(n) time, O(1) space!

function middleNode(head) {
  let slow = head
  let fast = head

  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next
  }

  return slow
}

// 1 → 2 → 3 → 4 → 5
// slow: 1 → 2 → 3 (stops here)
// fast: 1 → 3 → 5 → null

// When fast reaches end,
// slow is at middle!

Common Mistakes

• Losing reference to head (always keep track!)
• Not handling null/empty list edge cases
• Creating cycles accidentally during manipulation
• Forgetting to update both prev and next in doubly linked

Interview Tips

• Draw the pointers! Visualize before coding
• Use dummy head node to simplify edge cases
• Fast/slow pointer technique solves many problems
• Know trade-offs vs arrays: insert O(1) vs access O(n)

Practice Problems

Related Concepts