Time and space complexity for the data structures and sorting algorithms interviewers actually ask about.
| Name | Access | Search | Insert | Delete |
|---|---|---|---|---|
list (dynamic array) append is O(1) amortized; insert/pop at index 0 is O(n) | O(1) | O(n) | O(n) | O(n) |
dict / hash map O(n) worst case on pathological collisions | — | O(1) | O(1) | O(1) |
set same hashing behaviour as dict | — | O(1) | O(1) | O(1) |
deque O(1) at both ends — the reason to prefer it over list for queues | O(n) | O(n) | O(1) | O(1) |
heap (binary) O(1) access is peek at the root only | O(1) | O(n) | O(log n) | O(log n) |
balanced BST not built into Python — use `sortedcontainers` | O(log n) | O(log n) | O(log n) | O(log n) |
singly linked list insert/delete O(1) only once you hold the node | O(n) | O(n) | O(1) | O(1) |
string immutable — concatenation in a loop is O(n²) | O(1) | O(n) | O(n) | O(n) |
Complexities are for the average case unless the column says otherwise. When an interviewer asks “can you do better?”, they usually mean: can you trade space for time by adding a hash map?
