I run a service business·I build them

Data Structures

Linked Lists

Implement linked lists and master common patterns: reversal, cycle detection, and merging.

Linked Lists

A linked list is a sequence of nodes, each containing a value and a pointer to the next node.

Advantages over arrays:

  • O(1) insert/delete at any known position (no shifting)
  • Dynamic size

Disadvantages:

  • O(n) access by index (no random access)
  • Extra memory for pointers
  • Poor cache performance

Types

  • Singly linked: Each node has next only
  • Doubly linked: Each node has next and prev
  • Circular: Last node points back to first

Classic Problems

  • Reverse a linked list
  • Detect a cycle (Floyd's algorithm)
  • Find the middle
  • Merge two sorted lists

Example

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

// Helper: create list from array
function createList(arr) {
  if (!arr.length) return null;
  const head = new ListNode(arr[0]);
  let curr = head;
  for (let i = 1; i < arr.length; i++) {
    curr.next = new ListNode(arr[i]);
    curr = curr.next;
  }
  return head;
}

// Reverse linked list (iterative)
function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

// Find middle (fast/slow pointer)
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

// Detect cycle (Floyd's algorithm)
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

// Merge two sorted lists
function mergeSorted(l1, l2) {
  const dummy = new ListNode(0);
  let curr = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
    else { curr.next = l2; l2 = l2.next; }
    curr = curr.next;
  }
  curr.next = l1 || l2;
  return dummy.next;
}

// Nothing above runs on its own. Drive it, and print the lists as arrays so
// the pointer work is visible:
function toArray(head) {
  const out = [];
  for (let n = head; n; n = n.next) out.push(n.val);
  return out;
}

console.log("original:", toArray(createList([1, 2, 3, 4, 5])));
console.log("middle:", findMiddle(createList([1, 2, 3, 4, 5])).val);
console.log("reversed:", toArray(reverseList(createList([1, 2, 3, 4, 5]))));
console.log("merged:", toArray(mergeSorted(createList([1, 3, 5]), createList([2, 4, 6]))));
Try it yourself — JAVASCRIPT