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).
Lists
![[icon]](/wiki/File:Wiki_letter_w_cropped.svg?lang=en){kind=small} | This section needs expansion. You can help by adding to it. (March 2023) |
| Peek (index) |
Mutate (insert or delete) at … | Excess space, average | |||
|---|---|---|---|---|---|
| Beginning | End | Middle | |||
| Linked list | Θ(n) | Θ(1) | Θ(1), known end element; Θ(n), unknown end element |
Θ(n) | Θ(n) |
| Array | Θ(1) | — | — | — | 0 |
| Dynamic array | Θ(1) | Θ(n) | Θ(1) amortized | Θ(n) | Θ(n)[1] |
| Balanced tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) |
| Random-access list | Θ(log n)[2] | Θ(1) | —[2] | —[2] | Θ(n) |
| Hashed array tree | Θ(1) | Θ(n) | Θ(1) amortized | Θ(n) | Θ(√n) |
Maps
Maps store a collection of (key, value) pairs, such that each possible key appears at most once in the collection. They generally support three operations:[3]
- Insert: add a new (key, value) pair to the collection, mapping the key to its new value. Any existing mapping is overwritten. The arguments to this operation are the key and the value.
- Remove: remove a (key, value) pair from the collection, unmapping a given key from its value. The argument to this operation is the key.
- Lookup: find the value (if any) that is bound to a given key. The argument to this operation is the key, and the value is returned from the operation.
Unless otherwise noted, all data structures in this table require O(n) space.
 |
| Data structure | Lookup, removal | Insertion | Ordered | ||
|---|---|---|---|---|---|
| average | worst case | average | worst case | ||
| Hash table | O(1) | O(n) | O(1) | O(n) | No |
| B-tree[4] | 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 |
| Association list | O(n) | O(n) | O(1) | O(1) | No |
Notes
- ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo
- ^ a b c Chris Okasaki (1995). "Purely Functional Random-Access Lists". Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture: 86–95. doi:10.1145/224164.224187.
- ^ Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 81–98, archived (PDF) from the original on 2014-08-02
- ^ Cormen et al., p. 484.
References
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022-04-05). Introduction to Algorithms, fourth edition. MIT Press. ISBN 978-0-262-36750-9.