# Lesson 48: Mastering JavaScript Linked list with challenges!

A **linked list** is a linear data structure made of nodes, where each node has:

* `value`: the data the node holds
    
* `next`: a reference to the next node (or `null` if it's the last node)
    

```plaintext
let node = {
  value: 10,
  next: null
};
```

The head node is the entry point. Traversing requires walking node-by-node.

### 🆚 Compared to Arrays

| Feature | Array | Linked List |
| --- | --- | --- |
| Indexed Access | Fast (`O(1)`) | Slow (`O(n)`) |
| Insert at Beginning | Slow (`O(n)`) | Fast (`O(1)`) |
| Delete at Beginning | Slow (`O(n)`) | Fast (`O(1)`) |
| Memory locality | Contiguous | Non-contiguous |

### Enhancements

* **Doubly Linked List**: adds `prev` pointer
    
* **Tail Pointer**: fast access to last node
    
* **Circular Linked List**: last node points back to head
    

---

## 📉 2. Fill Gaps — Hidden Corners & Traps

* [`list.next`](http://list.next) `=` [`list.next.next`](http://list.next.next) skips over a node. If you're holding no references to the skipped node, it's eligible for **garbage collection**.
    
* Be cautious with **circular references** — they can cause infinite loops if not handled (e.g., [`node.next`](http://node.next) `= node`).
    
* Traversing a list is inherently **recursive** in structure — can be implemented iteratively or recursively, but deep recursion can cause stack overflow.
    

---

## 💻 3. Challenge Me Deeply — 10 Expert-Level Practice Problems

### 🧩 Challenge 1: Reverse a Singly Linked List (Iteratively)

```plaintext
function reverseList(head) {
  let prev = null, current = head;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}
```

### 🧩 Challenge 2: Detect a Cycle (Floyd's Tortoise and Hare)

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

### 🧩 Challenge 3: Find Middle Node

```plaintext
function middleNode(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}
```

### 🧩 Challenge 4: Merge Two Sorted Linked Lists

```plaintext
function mergeLists(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  if (l1.value < l2.value) {
    l1.next = mergeLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeLists(l1, l2.next);
    return l2;
  }
}
```

### 🧩 Challenge 5: Remove N-th Node From End

```plaintext
function removeNthFromEnd(head, n) {
  let dummy = { next: head };
  let fast = dummy, slow = dummy;

  for (let i = 0; i <= n; i++) fast = fast.next;
  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}
```

### 🧩 Challenge 6: Check if a List is a Palindrome

```plaintext
function isPalindrome(head) {
  let slow = head, fast = head;
  const stack = [];

  while (fast && fast.next) {
    stack.push(slow.value);
    slow = slow.next;
    fast = fast.next.next;
  }

  if (fast) slow = slow.next;

  while (slow) {
    if (stack.pop() !== slow.value) return false;
    slow = slow.next;
  }
  return true;
}
```

### 🧩 Challenge 7: Clone a Linked List With Random Pointers (advanced)

```plaintext
function copyRandomList(head) {
  let map = new Map();
  let current = head;

  while (current) {
    map.set(current, { value: current.value });
    current = current.next;
  }

  current = head;
  while (current) {
    let clone = map.get(current);
    clone.next = map.get(current.next) || null;
    clone.random = map.get(current.random) || null;
    current = current.next;
  }

  return map.get(head);
}
```

### 🧩 Challenge 8: Convert Array to Linked List and vice versa

```plaintext
function arrayToList(arr) {
  let head = null;
  for (let i = arr.length - 1; i >= 0; i--) {
    head = { value: arr[i], next: head };
  }
  return head;
}

function listToArray(head) {
  const result = [];
  while (head) {
    result.push(head.value);
    head = head.next;
  }
  return result;
}
```

### 🧩 Challenge 9: Recursive Length of List

```plaintext
function getLength(node) {
  return node ? 1 + getLength(node.next) : 0;
}
```

### 🧩 Challenge 10: Find Intersection of Two Lists

```plaintext
function getIntersection(l1, l2) {
  let a = l1, b = l2;
  while (a !== b) {
    a = a ? a.next : l2;
    b = b ? b.next : l1;
  }
  return a; // or null
}
```

---

## 💼 4. Interview-Ready Questions

### Conceptual

* **Q:** Why are linked lists better for queues than arrays?  
    **A:** Linked lists allow `O(1)` insertion/removal at both ends without reindexing.
    
* **Q:** When would you prefer a doubly linked list over singly?  
    **A:** When you need to traverse both forward and backward efficiently.
    
* **Q:** Why can’t we access the N-th element instantly in a linked list?  
    **A:** Because each node only knows about the next — you must traverse linearly.
    

### Coding

* Implement a linked list class with `append`, `prepend`, `delete`, `find`, and `toArray` methods.
    
* Detect and remove a cycle in a linked list.
    
* Design a real-time chat buffer using linked list to avoid expensive array operations.
    

---

## 🌍 5. Real-World Usage Examples

* **Undo/Redo Stack** in editors: typically implemented via doubly linked list.
    
* **Queue systems** (e.g., job schedulers, print queues).
    
* **Browser history navigation**.
    
* **Streaming data** (audio/video): when buffering using constant-time appends/removals.
    

---

## 🧠 6. Memory Aids & Visualization

### Linked List Mnemonic

> "Next Stops Point the Way"  
> 🧠 Think: Every node is a bus stop, and `next` points to the next destination.

### ASCII Diagram

```plaintext
[1] → [2] → [3] → [4] → null
```

---

## 🎮 7. Fun Project: Interactive Linked List Playground

Build a web-based **Linked List Visualizer** in JavaScript:

* Add, remove, reverse nodes
    
* Animate `next` pointers
    
* Show traversal and mid-search
    
* Toggle singly/doubly/circular mode
    

Frameworks: HTML/CSS/Canvas or React + D3.js

---

## ✅ Pro Tips

* Avoid linked lists for random-access tasks — arrays or typed arrays are better.
    
* For extremely large data pipelines (streaming, processing) where append/remove dominate, linked lists save memory churn.
    
* Use `null` carefully — a missed base case in recursive linked list problems can cause **stack overflow** or infinite loops.