Linked Lists Mastery

Unlike arrays, a Linked List does not use contiguous memory. Each element (Node) is a separate object on the Heap that contains a value and a Pointer to the next node. This makes insertions and deletions extremely efficient (O(1)) at the cost of slow random access (O(N)).

1. Types of Linked Lists

• Singly Linked: Each node points only to the 'Next' node. (Low memory, one-way travel).
• Doubly Linked: Each node points to both 'Next' and 'Previous'. (Higher memory, two-way travel). This is what .NET's LinkedList<T> uses.
• Circular Linked: The last node points back to the first node. (Used for round-robin scheduling).

2. When to use a Linked List?

Use it when you need to frequently add/remove items from the **Start** or **Middle** of a collection. In an array, adding to the start requires shifting every other element (O(N)). In a Linked List, you just swap two pointers (O(1)).

4. Interview Mastery

Q: "How do you detect a Cycle (Loop) in a Singly Linked List?"

Architect Answer: "We use **Floyd's Cycle-Finding Algorithm** (also known as the Tortoise and the Hare). We have two pointers. The Slow pointer moves 1 step; the Fast pointer moves 2 steps. If there is a cycle, the Fast pointer will eventually 'lap' the Slow pointer and they will meet. If the Fast pointer hits NULL, there is no cycle. It is an O(N) time and O(1) space solution."