🔗 JavaScript Linked List Basics

Node Class

class ListNode {
  constructor(val = 0, next = null) {
    this.val  = val;
    this.next = next;
  }
}

Build and Traverse

// Build: 1 → 2 → 3 → null
const head = new ListNode(1);
head.next  = new ListNode(2);
head.next.next = new ListNode(3);

// Traverse
let curr = head;
while (curr !== null) {
  console.log(curr.val);
  curr = curr.next;
}
// Output: 1 2 3

Time: O(n) | Space: O(n) storage

---

Doubly Linked List

class DListNode {
  constructor(val = 0) {
    this.val  = val;
    this.next = null;
    this.prev = null;
  }
}

---

Key Operations

Insert at Head — O(1)

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

Insert at Tail — O(n)

function insertAtTail(head, val) {
  const node = new ListNode(val);
  if (!head) return node;
  let curr = head;
  while (curr.next) curr = curr.next;
  curr.next = node;
  return head;
}

Delete by Value — O(n)

function deleteVal(head, val) {
  const dummy = new ListNode(0, head);
  let prev = dummy, curr = head;
  while (curr) {
    if (curr.val === val) { prev.next = curr.next; break; }
    prev = curr;
    curr = curr.next;
  }
  return dummy.next;
}

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

---

Q1 — Count Nodes

🧠 How to Approach This

Step 1 — Recognize the pattern: Simple traversal counter.

Step 2 — Brute force (what NOT to do): Spread into array, use .length — extra allocation.

Step 3 — Optimal insight: Single pointer walk.

Step 4 — Algorithm:

1. count = 0, curr = head

2. While curr: count++, curr = curr.next

3. Return count

Step 5 — Edge cases: Empty list → 0.

function countNodes(head) {
  let count = 0, curr = head;
  while (curr) { count++; curr = curr.next; }
  return count;
}

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

---

Q2 — Get Nth from Start

🧠 How to Approach This

Step 1 — Recognize the pattern: Walk n steps from head.

Step 2 — Brute force (what NOT to do): Collect to array, index — O(n) space.

Step 3 — Optimal insight: Direct traversal.

Step 4 — Algorithm:

1. Walk n steps

2. Return node.val or null

Step 5 — Edge cases: n >= list length → null.

function getNth(head, n) {
  let curr = head;
  for (let i = 0; i < n && curr; i++) curr = curr.next;
  return curr?.val ?? null;
}

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

---

The Dummy Head Trick

const dummy = new ListNode(0);
dummy.next = head;
// ... modifications ...
return dummy.next; // real head

Eliminates null-checks at the head. Used in 70%+ of linked list problems.

---

Array vs Linked List (JavaScript)

JS Note: Strings are immutable. For "in-place" style operations on characters, split into array → modify → join back.