Time Complexity of Data Structures

This is a quick reference for common data structure tradeoffs. Unless stated otherwise, $n$ is the number of stored elements, $m$ is the number of inserted or concatenated elements, $k$ is the key length, and hash table operations are average-case under a good hash function and normal load factor.

Random Access ADT

Random access means retrieving or updating the item at an index.

Data Structure	Access	Search	Insert begin	Insert middle	Insert end	Delete begin	Delete middle	Delete end	Concat	Space
Static array	$O(1)$	$O(n)$	$O(n)$	$O(n)$	$O(1)$ if space exists	$O(n)$	$O(n)$	$O(1)$	$O(n+m)$	$O(n)$
Dynamic array	$O(1)$	$O(n)$	$O(n)$	$O(n)$	$O(1)$ amortized	$O(n)$	$O(n)$	$O(1)$	$O(n+m)$	$O(n)$
Singly linked list	$O(n)$	$O(n)$	$O(1)$	$O(n)$	$O(1)$ with tail, $O(n)$ without	$O(1)$	$O(n)$	$O(n)$	$O(1)$ with tail	$O(n)$
Doubly linked list	$O(n)$	$O(n)$	$O(1)$	$O(n)$	$O(1)$ with tail	$O(1)$	$O(n)$	$O(1)$ with tail	$O(1)$ with tail	$O(n)$
Hashed array / hash map by index	$O(1)$ average	$O(n)$ by value	$O(1)$ average	$O(1)$ average if order does not matter	$O(1)$ average	$O(1)$ average	$O(1)$ average if order does not matter	$O(1)$ average	$O(n+m)$	$O(n)$
RRB tree / persistent vector	$O(\log n)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$ to $O(\log n)$ amortized	$O(\log n)$	$O(\log n)$	$O(1)$ to $O(\log n)$ amortized	$O(\log n)$	$O(n)$

Use arrays or dynamic arrays when index lookup and cache locality matter. Use linked lists when stable node identity and cheap splicing matter more than indexing. Use persistent vectors or RRB trees when old versions must remain usable after updates.

Stack ADT

A stack is last-in, first-out: push and pop happen at the same end.

Data Structure	Peek	Push	Pop	Search	Space
Dynamic array	$O(1)$	$O(1)$ amortized	$O(1)$	$O(n)$	$O(n)$
Singly linked list	$O(1)$	$O(1)$	$O(1)$	$O(n)$	$O(n)$

Dynamic arrays are usually the default stack implementation because they are compact and cache-friendly. Linked-list stacks are useful when node allocation or stable node references are part of the design.

Queue ADT

A queue is first-in, first-out: enqueue at the back and dequeue at the front.

Data Structure	Peek front	Enqueue	Dequeue	Search	Space
Circular buffer / ring buffer	$O(1)$	$O(1)$ amortized	$O(1)$	$O(n)$	$O(n)$
Singly linked list with head and tail	$O(1)$	$O(1)$	$O(1)$	$O(n)$	$O(n)$
Two-stack queue	$O(1)$ amortized	$O(1)$	$O(1)$ amortized	$O(n)$	$O(n)$

Use a ring buffer for a bounded or mostly bounded queue. Use a linked queue when the queue can grow unpredictably and pointer allocation cost is acceptable. Use two stacks when implementing a queue on top of stack primitives.

Deque ADT

A deque supports pushing and popping from both ends.

Data Structure	Access	Push front	Push back	Pop front	Pop back	Search	Space
Circular buffer	$O(1)$	$O(1)$ amortized	$O(1)$ amortized	$O(1)$	$O(1)$	$O(n)$	$O(n)$
Doubly linked list	$O(n)$	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(n)$	$O(n)$
Linked block deque	$O(1)$ to $O(\log n)$ depending on indexing	$O(1)$ amortized	$O(1)$ amortized	$O(1)$	$O(1)$	$O(n)$	$O(n)$

Circular buffers are fast and compact. Doubly linked lists make node splicing cheap. Linked block deques, like many standard-library deques, reduce the reallocation cost of large contiguous arrays.

Sorted Access ADT

Sorted access means maintaining an order so that minimum, maximum, range scans, predecessor, and successor queries are efficient.

Data Structure	Search	Insert	Delete	Min / Max	Predecessor / Successor	Range query of $r$ results	Concat / Merge	Space
Sorted array	$O(\log n)$	$O(n)$	$O(n)$	$O(1)$	$O(\log n)$	$O(\log n+r)$	$O(n+m)$	$O(n)$
Sorted linked list	$O(n)$	$O(n)$	$O(n)$	$O(1)$	$O(n)$	$O(n+r)$	$O(n+m)$	$O(n)$
Balanced BST	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$ or $O(1)$ cached	$O(\log n)$	$O(\log n+r)$	$O(n+m)$ usually	$O(n)$
Skip list	$O(\log n)$ expected	$O(\log n)$ expected	$O(\log n)$ expected	$O(1)$	$O(\log n)$ expected	$O(\log n+r)$ expected	$O(n+m)$ usually	$O(n)$
B-tree / B+ tree	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n+r)$	$O(n+m)$ usually	$O(n)$

Use sorted arrays when reads dominate writes. Use balanced trees or skip lists when inserts and deletes are common. Use B-trees and B+ trees when disk, pages, or cache-line-sized blocks matter.

Hash Table ADT

Hash tables optimize key lookup and update, not ordered traversal.

Operation	Average	Worst case
Insert	$O(1)$	$O(n)$
Lookup	$O(1)$	$O(n)$
Delete	$O(1)$	$O(n)$
Iterate all items	$O(n)$	$O(n)$
Resize / rehash	$O(n)$	$O(n)$
Ordered range query	$O(n)$	$O(n)$
Space	$O(n)$	$O(n)$

The worst case appears when many keys collide or when an implementation is forced to resize. Some hash maps use balanced trees inside buckets, which can improve collision-heavy lookup from $O(n)$ to $O(\log n)$.

Heap ADT

Heaps optimize repeated access to the highest or lowest priority item.

Data Structure	Find min / max	Insert	Extract min / max	Delete arbitrary item	Decrease / increase key	Merge	Space
Binary heap	$O(1)$	$O(\log n)$	$O(\log n)$	$O(n)$ unless indexed	$O(\log n)$ if indexed	$O(n+m)$	$O(n)$
d-ary heap	$O(1)$	$O({\log }_{d}n)$	$O(d{\log }_{d}n)$	$O(n)$ unless indexed	$O({\log }_{d}n)$ if indexed	$O(n+m)$	$O(n)$
Binomial heap	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
Fibonacci heap	$O(1)$	$O(1)$ amortized	$O(\log n)$ amortized	$O(\log n)$ amortized	$O(1)$ amortized	$O(1)$ amortized	$O(n)$

Binary heaps are the practical default priority queue. Fibonacci heaps matter mostly in algorithm analysis, especially when many decrease-key operations dominate extract-min operations.

Trie ADT

Tries optimize operations on strings or sequences by key length instead of by the number of keys.

Operation	Complexity	Notes
Insert key	$O(k)$	$k$ is the key length.
Lookup exact key	$O(k)$	Does not depend directly on $n$.
Delete key	$O(k)$	May also prune unused nodes.
Prefix lookup	$O(k)$	Find the node for the prefix.
Enumerate prefix results	$O(k+r)$	$r$ is the number of returned characters or keys.
Space	$O(\text{total characters})$	Can be high without compression.

Use a trie when prefix operations matter: autocomplete, lexicographic enumeration, routing tables, and dictionaries. Use a radix tree or compressed trie when long one-child chains waste too much memory.

By Use

Geographic Data

Use R-trees for rectangles and spatial indexes, quadtrees for recursively partitioned 2D space, k-d trees for nearest-neighbor queries over points, and geohashes when a spatial key needs to work with ordinary string or B-tree indexing.

Sorted Data

Use sorted arrays for mostly static data, balanced BSTs or skip lists for mutable in-memory sorted sets, and B-trees or B+ trees for database and filesystem indexes.

Least Frequently Used

An LFU cache usually combines a hash map from key to node with frequency buckets. With a hash map plus doubly linked lists per frequency, get, put, and eviction can be $O(1)$ average. With a min-heap, eviction is $O(\log n)$ and stale heap entries need cleanup.

Caching

An LRU cache usually combines a hash map with a doubly linked list: the hash map gives $O(1)$ average lookup, and the list gives $O(1)$ movement to the front and eviction from the back.

Indexing

Use hash indexes for exact-match lookup, B-tree indexes for ordered lookup and range scans, LSM-tree indexes for write-heavy storage engines, inverted indexes for text search, and bitmap indexes for low-cardinality analytical filters.

Text Editing

Use a gap buffer for single-cursor editing, a piece table for preserving original buffers and undo history, and a rope for very large text where concatenation, splitting, and substring operations need to stay efficient.