Data Representation
A linked list is a sequence of nodes where each node points to the next.
class ListNode:
def __init__(self, value: int, next: 'ListNode | None' = None):
self.value = value
self.next = next # Pointer to next node (or None for tail)vs Arrays
| Linked List | Array (Python list) | |
|---|---|---|
Access by index |
O(n) — must traverse |
O(1) — direct access |
Insert at head |
O(1) — change one pointer |
O(n) — shift all elements |
Insert at tail |
O(n) or O(1) with tail pointer |
O(1) amortized |
Delete |
O(1) if you have the node |
O(n) — shift elements |
Memory |
Extra space for pointers |
Contiguous, cache-friendly |
Key Patterns
-
Two pointers (fast/slow): Floyd’s cycle detection, find middle
-
Dummy head: Simplifies edge cases when the head might change
-
Reversal: Can you reverse a linked list? (YES — this is common)
Exercises
-
Reverse Linked List — Iterative + recursive
-
Detect Cycle — Floyd’s tortoise and hare