This is a comparison of data structures. All times are listed in big O notation.
O(1) is faster than O(log n) and it faster than O(n).
| Insert | Delete | Search | Find maximum | Space usage | |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) or O(1)[1] | O(n) or O(1)[2] | O(n) |
| Sorted Array | O(n) | O(n) | O(log n) | O(1) | O(n) |
| Linked list | O(1) | O(1) | O(n) | O(n) | O(n) |
| Sorted linked list | O(n) | O(n) | O(n) | O(1) | O(n) |
| Balanced binary tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(log n) | O(log n)[3] | O(n) | O(1) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) or O(1)[4] | O(n) |
Footnotes
- ^ if indexed by value - see control table,"trivial hash function" example
- ^ if indexed by value - see control table,"trivial hash function" example
- ^ Can only delete the max (or min in a min heap)
- ^ if "trivial hash function" possible