A Linked List is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element is a separate Node object that contains the data and a Pointer (reference) to the next node in the sequence.

Think of a Linked List as a Scavenger Hunt:

1. You have a clue (Data).
2. Attached to that clue is a map to the next location (Pointer).
3. To get to the 5th location, you must visit locations 1, 2, 3, and 4 first. You can't just teleport there.
4. If you lose the map to the next location, the rest of the hunt is lost!

---

Core Properties

• Dynamic Size: Can easily grow or shrink without expensive resizing (unlike arrays).
• Non-Contiguous: Nodes can be anywhere in memory.
• Sequential Access: No random access. To find the $n^{th}$ element, you must traverse from the head.

Complexity Analysis

---

javascript Standard
/**
 * A Single Node in the List
 */
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null; // Pointer to the next node
  }
}

/**
 * Basic Linked List Operations
 */
class LinkedList {
  constructor() {
    this.head = null;
  }

  // Add to the front - O(1)
  prepend(value) {
    const newNode = new ListNode(value);
    newNode.next = this.head;
    this.head = newNode;
  }

  // Reverse the list - O(n) time, O(1) space
  reverse() {
    let prev = null;
    let curr = this.head;
    
    while (curr) {
      const nextTemp = curr.next; // Store next
      curr.next = prev;          // Reverse pointer
      prev = curr;               // Move prev forward
      curr = nextTemp;           // Move curr forward
    }
    
    this.head = prev;
  }
}

---

Top Techniques

• Dummy Head: Use a temporary node dummy = new ListNode(0) whose next points to the head. This simplifies edge cases like deleting the head.
• Two Pointers: Used for finding midpoints, detecting cycles, or finding the $k^{th}$ node from the end.

Common Questions

• Reverse a Linked List (Iterative & Recursive).
• Merge two sorted linked lists.
• Remove $n^{th}$ node from the end.
• Intersection of two linked lists.
• Palindrome Linked List. Blackwell