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).
A list or sequence is an abstract data type that represents a finite number of ordered values, where the same value may occur more than once. Lists generally support the following operations:
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)[1][2] | Θ(n) |
Array | Θ(1) | — | — | — | 0 |
Dynamic array | Θ(1) | Θ(n) | Θ(1) amortized | Θ(n) | Θ(n)[3] |
Balanced tree | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) |
Random-access list | Θ(log n)[4] | Θ(1) | —[4] | —[4] | Θ(n) |
Hashed array tree | Θ(1) | Θ(n) | Θ(1) amortized | Θ(n) | Θ(√n) |
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:[5]
Unless otherwise noted, all data structures in this table require O(n) space.
This list is incomplete; you can help by adding missing items. (March 2023) |
Data structure | Lookup, removal | Insertion | Ordered | ||
---|---|---|---|---|---|
average | worst case | average | worst case | ||
Association list | O(n) | O(n) | O(1) | O(1) | No |
B-tree[6] | O(log n) | O(log n) | O(log n) | O(log n) | Yes |
Hash table | O(1) | O(n) | O(1) | O(n) | No |
Unbalanced binary search tree | O(log n) | O(n) | O(log n) | O(n) | Yes |
Some map data structures offer superior performance in the case of integer keys. In the following table, let m be the number of bits in the keys.
Data structure | Lookup, removal | Insertion | Space | ||
---|---|---|---|---|---|
average | worst case | average | worst case | ||
Fusion tree | [?] | O(log m n) | [?] | [?] | O(n) |
Van Emde Boas tree | O(log log m) | O(log log m) | O(log log m) | O(log log m) | O(m) |
X-fast trie | O(n log m)[a] | [?] | O(log log m) | O(log log m) | O(n log m) |
Y-fast trie | O(log log m)[a] | [?] | O(log log m)[a] | [?] | O(n) |
A priority queue is an abstract data-type similar to a regular queue or stack. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. Priority queues support the following operations:
Priority queues are frequently implemented using heaps.
A (max) heap is a tree-based data structure which satisfies the heap property: for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C.
In addition to the operations of an abstract priority queue, the following table lists the complexity of two additional logical operations:
Here are time complexities[7] of various heap data structures. Function names assume a max-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
Operation | find-max | delete-max | insert | increase-key | meld |
---|---|---|---|---|---|
Binary[7] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
Binomial[7][8] | Θ(1) | Θ(log n) | Θ(1)[a] | Θ(log n) | O(log n) |
Skew binomial[9] | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) | O(log n)[b] |
Pairing[10] | Θ(1) | O(log n)[a] | Θ(1) | o(log n)[a][c] | Θ(1) |
Rank-pairing[13] | Θ(1) | O(log n)[a] | Θ(1) | Θ(1)[a] | Θ(1) |
Fibonacci[7][14] | Θ(1) | O(log n)[a] | Θ(1) | Θ(1)[a] | Θ(1) |
Strict Fibonacci[15] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
Brodal[16][d] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
2–3 heap[18] | O(log n) | O(log n)[a] | O(log n)[a] | Θ(1) | ? |