Clue 1: "Look under the big tree" → Points to Clue 2
Clue 2: "Check the mailbox" → Points to Clue 3
Clue 3: "Open the red box" → Points to Treasure!

[Car 1] → [Car 2] → [Car 3] → [Car 4] → null
  Data      Data      Data      Data

const array = ["A", "B", "C", "D"];
//             0    1    2    3  ← Can jump to any index!

console.log(array[2]); // "C" - Direct access!

// Can't jump to middle! Must follow the chain!
Head → [A] → [B] → [C] → [D] → null

// To get to C, must go: Head → A → B → C

class Node {
  constructor(data) {
    this.data = data; // The value
    this.next = null; // Pointer to next node
  }
}

// Create nodes
const node1 = new Node("A");
const node2 = new Node("B");
const node3 = new Node("C");

// Connect them!
node1.next = node2; // A → B
node2.next = node3; // B → C

// Now we have: A → B → C → null

console.log(node1.data); // "A"
console.log(node1.next.data); // "B"
console.log(node1.next.next.data); // "C"

class LinkedList {
  constructor() {
    this.head = null; // Start of the list
    this.size = 0; // Number of nodes
  }

  // Add to the end
  append(data) {
    const newNode = new Node(data);

    // If list is empty
    if (!this.head) {
      this.head = newNode;
      this.size++;
      return;
    }

    // Find the last node
    let current = this.head;
    while (current.next) {
      current = current.next;
    }

    // Add new node at the end
    current.next = newNode;
    this.size++;
  }

  // Add to the beginning
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // Insert at specific position
  insertAt(data, index) {
    if (index < 0 || index > this.size) {
      return false;
    }

    // Insert at beginning
    if (index === 0) {
      this.prepend(data);
      return true;
    }

    const newNode = new Node(data);
    let current = this.head;
    let previous = null;
    let count = 0;

    // Find position
    while (count < index) {
      previous = current;
      current = current.next;
      count++;
    }

    // Insert node
    newNode.next = current;
    previous.next = newNode;
    this.size++;
    return true;
  }

  // Remove from specific position
  removeAt(index) {
    if (index < 0 || index >= this.size) {
      return null;
    }

    let current = this.head;

    // Remove first node
    if (index === 0) {
      this.head = current.next;
      this.size--;
      return current.data;
    }

    let previous = null;
    let count = 0;

    // Find node to remove
    while (count < index) {
      previous = current;
      current = current.next;
      count++;
    }

    // Remove node
    previous.next = current.next;
    this.size--;
    return current.data;
  }

  // Get data at index
  getAt(index) {
    if (index < 0 || index >= this.size) {
      return null;
    }

    let current = this.head;
    let count = 0;

    while (count < index) {
      current = current.next;
      count++;
    }

    return current.data;
  }

  // Print the list
  print() {
    let current = this.head;
    const values = [];

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

    console.log(values.join(" → ") + " → null");
  }

  // Clear the list
  clear() {
    this.head = null;
    this.size = 0;
  }
}

// Let's use it!
const list = new LinkedList();
list.append("A");
list.append("B");
list.append("C");
list.print(); // A → B → C → null

list.prepend("Start");
list.print(); // Start → A → B → C → null

list.insertAt("Middle", 2);
list.print(); // Start → A → Middle → B → C → null

list.removeAt(2);
list.print(); // Start → A → B → C → null

null ← [A] ⇄ [B] ⇄ [C] ⇄ [D] → null

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

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

  // Add to end
  append(data) {
    const newNode = new DoublyNode(data);

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

    this.size++;
  }

  // Add to beginning
  prepend(data) {
    const newNode = new DoublyNode(data);

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

    this.size++;
  }

  // Print forward
  printForward() {
    let current = this.head;
    const values = [];

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

    console.log("Forward: " + values.join(" ⇄ "));
  }

  // Print backward
  printBackward() {
    let current = this.tail;
    const values = [];

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

    console.log("Backward: " + values.join(" ⇄ "));
  }
}

// Let's use it!
const dList = new DoublyLinkedList();
dList.append("A");
dList.append("B");
dList.append("C");

dList.printForward(); // Forward: A ⇄ B ⇄ C
dList.printBackward(); // Backward: C ⇄ B ⇄ A

class BrowserHistory {
  constructor() {
    this.list = new DoublyLinkedList();
    this.current = null;
  }

  visit(url) {
    this.list.append(url);
    this.current = this.list.tail;
    console.log(`Visiting: ${url}`);
  }

  back() {
    if (this.current && this.current.prev) {
      this.current = this.current.prev;
      console.log(`Back to: ${this.current.data}`);
    } else {
      console.log("No previous page!");
    }
  }

  forward() {
    if (this.current && this.current.next) {
      this.current = this.current.next;
      console.log(`Forward to: ${this.current.data}`);
    } else {
      console.log("No next page!");
    }
  }
}

class Playlist {
  constructor() {
    this.list = new LinkedList();
    this.current = null;
  }

  addSong(song) {
    this.list.append(song);
    if (!this.current) {
      this.current = this.list.head;
    }
  }

  next() {
    if (this.current && this.current.next) {
      this.current = this.current.next;
      console.log(`Now playing: ${this.current.data}`);
    } else {
      console.log("End of playlist!");
    }
  }

  currentSong() {
    return this.current ? this.current.data : "No song playing";
  }
}

const playlist = new Playlist();
playlist.addSong("Song 1");
playlist.addSong("Song 2");
playlist.addSong("Song 3");

console.log(playlist.currentSong()); // Song 1
playlist.next(); // Now playing: Song 2
playlist.next(); // Now playing: Song 3

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

  while (current) {
    const nextTemp = current.next; // Save next
    current.next = prev; // Reverse pointer
    prev = current; // Move prev forward
    current = nextTemp; // Move current forward
  }

  return prev; // New head
}

// Visual:
// Before: 1 → 2 → 3 → null
// After:  3 → 2 → 1 → null

function findMiddle(head) {
  let slow = head;
  let fast = head;

  // Fast moves 2x speed of slow
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow; // Slow is at middle!
}

// Visual:
// 1 → 2 → 3 → 4 → 5
//         ↑
//       Middle

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; // Cycle detected!
    }
  }

  return false;
}

function mergeSorted(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;
  }

  // Attach remaining nodes
  current.next = l1 || l2;

  return dummy.next;
}

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

  let first = dummy;
  let second = dummy;

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

  // Move both until first reaches end
  while (first) {
    first = first.next;
    second = second.next;
  }

  // Remove node
  second.next = second.next.next;

  return dummy.next;
}

function deleteNode(node) {
  // Your code here!
  // Hint: Copy next node's data!
}

// Example:
// List: 1 → 2 → 3 → 4
// Delete node with value 3
// Result: 1 → 2 → 4

function isPalindrome(head) {
  // Your code here!
  // Hint: Find middle, reverse second half, compare!
}

// Example:
// 1 → 2 → 2 → 1 → true
// 1 → 2 → 3 → false

function removeDuplicates(head) {
  // Your code here!
}

// Example:
// 1 → 1 → 2 → 3 → 3 → null
// Result: 1 → 2 → 3 → null

// ❌ Wrong - lost the head!
let current = head;
head = head.next; // Lost first node!

// ✅ Right - keep head safe
let current = head;
while (current) {
  current = current.next;
}

// ❌ Wrong - crashes if empty
function getFirst(head) {
  return head.data; // Error if head is null!
}

// ✅ Right - check first
function getFirst(head) {
  if (!head) return null;
  return head.data;
}

// ❌ Wrong - infinite loop if there's a cycle
let current = head;
while (current) {
  current = current.next; // Never ends if cycle!
}

// ✅ Right - use cycle detection first
if (!hasCycle(head)) {
  let current = head;
  while (current) {
    current = current.next;
  }
}

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

// Linked List Operations
list.append(data); // Add to end
list.prepend(data); // Add to beginning
list.insertAt(data, i); // Insert at position
list.removeAt(i); // Remove at position
list.getAt(i); // Get data at position
list.print(); // Display list

// Common Patterns
reverseList(head); // Reverse
findMiddle(head); // Find middle
hasCycle(head); // Detect cycle
mergeSorted(l1, l2); // Merge two lists
removeNth(head, n); // Remove nth from end