Comparison of data structures explained

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

See also: List (abstract data type).

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.

Maps

See also: Associative array.

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:

• 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	style=min-width:5em;max-width:5em	worst case	average		style=min-width:5em;max-width:5em	worst case
Association list	O(n)	O(n)	O(1)	O(1)
B-tree	O(log n)	O(log n)	O(log n)	O(log n)
Hash table	O(1)	O(n)	O(1)	O(n)
Unbalanced binary search tree	O(log n)	O(n)	O(log n)	O(n)

Integer keys

Some map data structures offer superior performance in the case of integer keys. In the following table, let be the number of bits in the keys.

Data structure	Lookup, removal		Insertion		Space
	average	style=min-width:5em;max-width:5em	worst case	average		style=min-width:5em;max-width:5em	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)		O(log log m)	O(log log m)	O(n log m)
Y-fast trie	O(log log m)		O(log log m)		O(n)

Priority queues

See also: Priority queue.

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

See also: Heap (data structure).

A (max) heap is a tree-based data structure which satisfies the : 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.

References

• Book: Cormen . Thomas H. . Introduction to Algorithms, fourth edition . Leiserson . Charles E. . Rivest . Ronald L. . Stein . Clifford . 2022-04-05 . MIT Press . 978-0-262-36750-9 . en.