| Search DS | Insert | Delete | Balance | Get at index | Search | Find minimum | Find maximum | Space usage |
|---|---|---|---|---|---|---|---|---|
| Unsorted array | O(1) | O(1) | N/A | O(1) | O(n) | O(n) | O(n) | O(n) |
| Sorted array | O(n) | O(n) | N/A | O(1) | O(log n) | O(1) | O(1) | O(n) |
| Unsorted linked list | O(1) | O(1) | N/A | O(n) | O(n) | O(n) | O(n) | O(n) |
| Sorted linked list | O(n) | O(1) | N/A | O(n) | O(n) | O(1) | O(1) | O(n) |
| Self-balancing binary tree | O(log n) | O(log n) | O(log n) | N/A | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(log n) | O(log n) | O(log n) | N/A | O(n) | O(1) for a min-heap O(n) for a max-heap | O(1) for a max-heap O(n) for a min-heap | O(n) |
| Hash table | O(1) | O(1) | O(n) | N/A | O(1) | O(n) | O(n) | O(n) |
| Trie (k = average length of key) | O(k) | O(k) | N/A | O(k) | O(k) | O(k) | O(k) | O(k n) |
