This is a comparison of data structures. All times are listed in big O notation
| Insert | Delete | Search | Find maximum | Space usage | |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | 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(1) | 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)[1] | O(n) | O(1) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) |
Footnotes
- ^ Can only delete the max (or min in a min heap)