Back to Topics
Linked List
A linked list is a sequence of nodes where each node holds a value and a pointer to the next node. Unlike arrays, nodes are scattered in memory, so random access is O(n). However, insertion and deletion at a known position are O(1) — no shifting needed. Two-pointer (fast/slow) techniques solve many linked-list problems elegantly.
Key Ideas
- No random access — traversal from head is always O(n)
- Insertion/deletion at a known node is O(1) — just rewire pointers
- Sentinel (dummy) head node simplifies edge cases at the list head
- Fast/slow pointers (Floyd's cycle detection): fast moves 2 steps, slow moves 1
- Reversing a list in-place uses three pointers: prev, curr, next
- Doubly linked list allows O(1) deletion given a node reference (used in LRU cache)
Complexity
| Operation | Time | Space |
|---|---|---|
| Access by index | O(n) | O(1) |
| Search | O(n) | O(1) |
| Insert at head | O(1) | O(1) |
| Insert at known node | O(1) | O(1) |
| Delete at known node | O(1) | O(1) |
Common Patterns
Fast / Slow PointersDetect cycles (Floyd's), find middle node, or find the n-th node from end.
Dummy Head NodePrepend a sentinel node to avoid special-casing insertions/deletions at the head.
In-place ReversalReverse a sublist by re-linking nodes with three pointers (prev, curr, next).
Merge Two ListsCompare heads and advance the pointer to the smaller node — used in merge sort.
Code Example
Detect cycle — Floyd's algorithmpython
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode | None) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False💡
When you see 'cycle', 'middle', or 'nth from end', draw the fast/slow pointer pattern first.