The ultimate data

structure cheat
sheet
Arrays, strings, linked lists, stacks & queues,
trees, graphs, maps, and heaps
 Time complexity:

Worst Case Scenario Average Case Best Case Scenario

Scenario

Accessing an O(1) O(1) O(1)

element

Updating an O(1) O(1) O(1)

element

Deleting an O(n) O(n) O(1)

element

Inserting an O(n) O(n) O(1)

element

Searching for O(n) O(n) O(1)

an element

Arrays Algorithm complexity:

Time Complexity Space

Complexity
(Space-Time complexity) Worst Case Average Case Best Case

Quicksort O(n2) O(n log(n)) O(n log(n)) O(log(n))

Mergesort O(n log(n)) O(n log(n)) O(n log(n)) O(n)

Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)

Bubble Sort O(n2) O(n2) O(n) O(1)

Insertion Sort O(n2) O(n2) O(n) O(1)

Selection Sort O(n2) O(n2) O(n2) O(1)

Binary Search O(log(n)) O(log(n)) O(1) O(1)

Linear Search O(n) O(n) O(1) O(1)

 Time complexity:
Worst Case Average Case Best Case Scenario
Scenario Scenario

Accessing O(1) O(1) O(1)

Deleting O(n) O(n) O(1)

Inserting O(n) O(n) O(1)

Searching O(n * m) O(n) O(1)

(n = string length
m = pattern length)

Slicing O(n) O(n) O(n)

(n = string length)

Concatenating O(n + m) O(n + m) O(n)

(n, m = string lengths)

Comparison O(n) O(n) O(n)

Strings
(n = shorter string length)

Inserting (Trie) O(m) O(m) O(1)

(m = key length)
(Space-time complexity)
Searching (Trie) O(m) O(m) O(1)
(m = key length)

Algorithm complexity:
Time Complexity Space
Complexity
Worst Case Average Best Case
Case

Radix sort O(n * m) O(n * m) O(n * m) O(n + m)

(m = longest string length)

Naive string search O(m*(n-m+1)) O(n * m) O(n) O(1)

(m = size of pattern)

Knuth-Morris-Pratt search O(m + n) O(n) O(n) O(m)

Boyer-Moore string search O(n * m) O(n) O(n/m) O(m)

Rubin-Karp Algorithm O(m*(n-m+1)) O(n + m) O(m) O(m)

 Time complexity:

Worst Case Average Case Best Case Scenario

Scenario Scenario

Delete (Stack) O(1) O(1) O(1)

Insert (Stack) O(1) O(1) O(1)

Search (Stack) O(n) O(n) O(1)

Peek/Top (Stack) O(1) O(1) O(1)

Stacks & Delete (Queue) O(1) O(1) O(1)

Queues Insert (Queue) O(1) O(1) O(1)

Search (Queue) O(n) O(n) O(1)

(Space-time complexity)

Algorithm Complexity:

Time Complexity Space

Complexity

Worst Case Average Case Best Case

Linear Search O(n) O(n) O(1) O(1)

Stack: LIFO (Last In First Out)

Queue: FIFO (First In First Out)

 Time complexity:

Worst Case Scenario Average Case Scenario Best Case Scenario

Accessing O(n) O(n) O(1)

Deleting O(1) O(1) O(1)

(after search)

Inserting O(1) O(1) O(1)

(after search)

Searching O(n) O(n) O(1)

Traversing O(n) O(n) O(n)

Linked
Access (Skip List) O(n) O(log n) O(log n)

Delete (Skip List) O(n) O(log n) O(log n)

Lists Insert (Skip List)

Search (Skip List)

O(n)

O(n)
O(log n)

O(log n)
O(log n)

O(log n)
(Space-time complexity)

Algorithm Complexity:

Time Complexity Space Complexity

Worst Case Average Case Best Case

Mergesort O(n log n) O(n log n) O(n log n) O(n)

Bubble Sort O(n²) O(n²) O(n) O(1)

Selection Sort O(n²) O(n²) O(n²) O(1)

Insertion Sort O(n²) O(n²) O(n) O(1)

Linear Search O(n) O(n) O(1) O(1)

 Time complexity:

Worst Case Average Case Best Case

Scenario Scenario Scenario

Binary Search Delete O(n) O(log n) O(log n)

Tree,
Cartesian Tree,
KD Tree Insert O(n) O(log n) O(log n)

Search O(n) O(log n) O(log n)

B-Tree, Delete O(log n) O(log n) O(log n)

Red-Black Tree,
Splay Tree,
AVL Tree Insert O(log n) O(log n) O(log n)

Search O(log n) O(log n) O(log n)

Trees Traversal O(n) O(n) O(n)

(Space-time complexity)

Algorithm Complexity:

Time Complexity Space

Complexity
Worst Case Average Best Case
Case

Depth-First Search O(n) O(n) O(n) O(n)

(In-order, pre-order, and
post-order traversal)

Breadth-First Search O(n) O(n) O(n) O(n)

(Level-order traversal)

Tree Sort O(n2) O(n log n) O(n log n) O(n)

Splaysort O(n log n) O(n log n) O(n) O(n)

Cartesian Tree Sort O(n log n) O(n log n) O(n) O(n)

 Time Complexity:

Worst Case Average Case Best Case

Scenario Scenario Scenario

Insert Vertex Adjacency List O(1) O(1) O(1)

Adjacency Matrix O(V2) O(V2) O(V2)

Incidence Matrix O(V*E) O(V*E) O(V*E)

Remove Vertex Adjacency List O(E) O(E) O(E)

Adjacency Matrix O(V2) O(V2) O(V2)

Incidence Matrix O(V*E) O(V*E) O(V*E)

Insert Edge Adjacency List O(1) O(1) O(1)

Adjacency Matrix O(1) O(1) O(1)

Incidence Matrix O(V*E) O(V*E) O(V*E)

Graphs
Remove Edge Adjacency List O(V) O(V) O(V)

Adjacency Matrix O(1) O(1) O(1)

Incidence Matrix O(V*E) O(V*E) O(V*E)

(Space-time complexity)
Check if Adjacency List O(V) O(V) O(V)
Vertices
Adjacent Adjacency Matrix O(1) O(1) O(1)

Incidence Matrix O(E) O(E) O(E)

Algorithm Complexity:

Time Complexity Space Complexity

Worst Case Average Best Case

Case

Breadth-First Search O(V+E) O(V+E) O(V+E) O(V)

Depth-First Search O(V+E) O(V+E) O(V+E) O(V)

A* Search O(E) O(E) O(E) O(V)

Dijkstra’s algorithm O(V2) O(E * log(V)) O(E * log(V)) O(V)

Floyd–Warshall O(V3) O(V3) O(V3) O(V2)

 Time complexity:

Worst Case Average Case Best Case Scenario

Scenario Scenario

Updating an element O(n) O(1) O(1)

Inserting an element O(n) O(1) O(1)

Deleting an element O(n) O(1) O(1)

Searching for an O(n) O(1) O(1)

element

Insert (TreeMap) O(log n) O(log n) O(1)

Delete (TreeMap) O(log n) O(log n) O(1)

Maps
Search (TreeMap) O(log n) O(log n) O(1)

(Space-time complexity) Algorithm Complexity:

Time Complexity Space

Complexity
Worst Case Average Case Best Case

Bucket Sort O(n2) O(n + k) O(n + k) O(n)

(k = buckets)

Insertion Sort O(n2) O(n2) O(n) O(1)

Selection Sort O(n2) O(n2) O(n2) O(1)

Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)

Hash-based Search O(n) O(1) O(1) O(1)

Binary Search O(log(n)) O(log(n)) O(1) O(1)

Linear Search O(n) O(n) O(1) O(1)

Rabin-Karp Algorithm O(m*(n-m+1)) O(n + m) O(m) O(m)

 Time complexity:

Worst Case Average Case Best Case Scenario

Scenario Scenario

Insert O(log n) O(logn) O(1)

Delete O(log n) O(log n) O(1)

Find min/max O(1) O(1) O(1)

Search O(n) O(n) O(1)

Insert O(log n) O(1) O(1)

(Fibonacci/Binomial)

Increase/Decrease key O(log n) O(log n) O(1)

Heaps Extract min/max O(log n) O(log n) O(log n)

(Space-time complexity)

Algorithm Complexity:

Time Complexity Space

Complexity
Worst Case Average Best Case
Case

Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)

Smoothsort O(n log(n)) O(n log(n)) O(n) O(n)

Quick select O(n2) O(n) O(n) O(1)

Linear Search O(n) O(n) O(1) O(1)

Dijkstra’s shortest O(V2) O(E * log(V)) O(E * log(V)) O(V)

path