Time Complexity of Data Structures

Random Access ADT

Data Structure	Access	Search	Insertion/begin/end	Deletion/begin/end	Concat	Space
Array	$O(1)$	$O(n)$	$O(n)$ / $O(N)$ / $O(1)$	$O(N)$ / $O(N)$ / $O(1)$	$O(n)$	$O(n)$
Catenable Sorted Lists	$O(logN)$	$O(\log N)$	$O(logN)$ / $O(1)$ / $O(1)$	$O(logN)$ / $O(1)$ / $O(1)$	$O(1)$	$O(n)$
RRB Trees	$O(logN)$	$O(logN)$	$O(logN)$ / $O(1)$ / $O(1)$	$O(logN)$ / $O(1)$ / $O(1)$	$O(logN)$	$O(n)$
Singly Linked List	$O(N)$	$O(N)$	$O(N)$ / $O(1)$ / $O(1)$	$O(N)$ / $O(1)$ / $O(1)$	$O(1)$	$O(N)$
Doubly Linked List	$O(N)$	$O(N)$	$O(N)$ / $O(1)$ / $O(1)$	$O(N)$ / $O(1)$ / $O(1)$	$O(1)$	$O(N)$
Hash List	$O(1)$	$O(1)$	$O(1)$ / $O(1)$ / $O(1)$	$O(1)$ / $O(1)$ / $O(1)$	$O(N)$	$O(N)$

Stack ADT

Queue ADT

Deque ADT

Sorted Access ADT

Data Structure	Access	Search	Insertion/ at End	Deletion/ at end	Concat	Space
Array	$O(1)$	$O(n)$	$O(n)$ / $O(1)$	$O(n)$ / $O(1)$	$O(n)$	$O(n)$
Catenable Sorted Lists	$O(logN)$	$O(logN)$	$O(logN)$ / $O(1)$	$O(logN)$ / $O(1)$	$O(1)$	$O(n)$
RRB Trees	$O(logN)$	$O(logN)$	$O(logN)$ / $O(1)$	$O(logN)$ / $O(1)$	$O(logN)$	$O(n)$

Hash Tables ADT

Heap ADT

Trie ADT

By Use

Geographic Data

Sorted Data

Least Frequently Used

Caching

Indexing

Text Editing