Top Qs
Timeline
Chat
Perspective
Comparison of data structures
From Wikipedia, the free encyclopedia
Remove ads
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).
Remove ads
Lists
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: access the element at a given index.
- insert: insert a new element at a given index. When the index is zero, this is called prepending; when the index is the last index in the list it is called appending.
- delete: remove the element at a given index.
Remove ads
Maps
Summarize
Perspective
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.
![]() |
Integer keys
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.
Remove ads
Priority queues
Summarize
Perspective
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:
- insert: add an element to the queue with an associated priority.
- find-max: return the element from the queue that has the highest priority.
- delete-max: remove the element from the queue that has the highest priority.
Priority queues are frequently implemented using heaps.
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:
- increase-key: updating a key.
- meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.
Here are time complexities[5] of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a max-heap.
- For persistent heaps (not supporting increase-key), a generic transformation reduces the cost of meld to that of insert, while the new cost of delete-max is the sum of the old costs of delete-max and meld.[11] Here, it makes meld run in Θ(1) time (amortized, if the cost of insert is) while delete-max still runs in O(log n). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.[10]
- Brodal queues and strict Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a persistent data structure achieving the same optimum, except that increase-key is not supported.
Remove ads
Notes
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads