Linked list
Frequent insertions and removals at positions you already hold, such as an LRU cache paired with a hash map.
Medium interview relevanceRoadmap: Intermediate
| Time | Insert or delete at a known node O(1); search O(n) |
|---|---|
| Space | O(n) |
Why it costs this much
Changing one or two pointers splices a node in or out, and no other node moves.
Code
def insert_after(node, value):
node.next = Node(value, node.next) # O(1): rewire two pointers
def find(head, target):
while head and head.val != target: # O(n): must walk from the head
head = head.next
return headCommon pitfalls
Reaching a position costs O(n). Pointer-chasing is also slow on real hardware, so arrays often win in practice.
Operation by operation
| Operation | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linked list insert or delete at a known node | O(1) | O(1) | O(1) | O(1) |
| Linked list search | O(1) | O(n) | O(n) | O(1) |
Linked list insert or delete at a known node. You already hold a pointer to the node (or its predecessor for a singly linked list). Finding the node first is O(n).
Linked list search. Target equally likely to be anywhere. Poor cache locality makes it slower than an array scan of the same size.