Data Structure Operation Complexity
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1)* | O(1)* |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash Table | N/A | O(1) avg | O(1) avg | O(1) avg |
| Heap (min/max) | O(1) min | O(n) | O(log n) | O(log n) |
* With pointer to the node. Without pointer, O(n) to find it first.