Comparison of data structures
This is a comparison of the performance of notable data structures, as measured by the complexity of their logical operations. For a more comprehensive listing of data structures, see List of data structures.
The comparisons in this article are organized by abstract data type. As a single concrete data structure may be used to implement many abstract data types, some data structures may appear in multiple comparisons (for example, a hash map can be used to implement an associative array or a set).
Maps
| Data structure | Lookup, removal | Insertion | Ordered | ||
|---|---|---|---|---|---|
| average | worst case | average | worst case | ||
| Hash table | O(1) | O(n) | O(1) | O(n) | No |
| Self-balancing binary search tree | O(log n) | O(log n) | O(log n) | O(log n) | Yes |
| Unbalanced binary search tree | O(log n) | O(n) | O(log n) | O(n) | Yes |
| Sequential container of key–value pairs (e.g. association list) |
O(n) | O(n) | O(1) | O(1) | No |