02. Linked Lists

Linked lists are a contiguous data structure, unlike arrays and strings, which are linear structures.
Each element (node) contains a value and a pointer/reference to the next node.

Efficient insertions and deletions:
- Adding or removing items from the beginning of a list is O(1).
- Avoids the need for shifting elements, unlike arrays.

Commonly used for problems such as:
- Detecting cycles in a linked list.
- Finding the middle element.
- Removing the nth node from the end.
Involves two pointers:
- Fast pointer: Moves two steps at a time.
- Slow pointer: Moves one step at a time.

Recursion provides a clean way to solve problems like:
- Reversing a linked list.
- Detecting palindromes.
- Merging sorted linked lists.
Drawbacks of Recursion:
- Uses O(N) space due to the recursive call stack.
- Recursive solutions can be converted to iterative solutions for better space efficiency, but this may increase code complexity.

Understand the Node Structure:
- Each node typically contains value and next fields.
- For doubly linked lists, nodes also have a prev field.
Plan Pointer Manipulation Carefully:
- Visualize pointer movements to avoid errors like losing a reference to a node.
Use Dummy Nodes for Simplicity:
- Simplifies edge cases (e.g., modifying the head node).
Break Down Problems into Smaller Steps:
- Handle individual tasks like traversing the list, reversing pointers, or updating node connections.
Leverage Two Pointers or Recursion:
- Two-pointer techniques and recursion are common tools for efficient solutions.

Many problems involve traversing the list while modifying pointers or creating new lists.
Key operations to master:
- Reversing a list.
- Merging or splitting lists.
- Detecting cycles.
Always consider edge cases like:
- Empty lists.
- Single-node lists.
- Lists with cycles.

🌱 Keegan's Digital Garden