Search data structure
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(1) | O(1) | O(n) | O(n) | O(n) |
| Binary search tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(log n) | O(1)† | N/A | O(1) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(2n) |
† Can only delete the max (or min in a min heap)