Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data structure (Algorithms (Sort (QuickSort (pivot, cursor low and high,…
Data structure
Algorithms
fib
maths
matrix
opti O(logn) O(1)
O(N) O(1)
DP space opti
O(N) O(1)
last 2
DP + storage
O(n)
brute force rec
O(2^n)
Split str
ranges
c++ 20
boost::split
stream
getline
delim
istream_iterator
delim
dynamic prog
memorization
tabulation
Sort
Insertion Sort
iteration
remove and insert
repeat until no element left
O(n^2)
Bubble sort
while swap
compare and swap
O(n^2)
very slow
Merge Sort
divide and conquer
recursive dividing
O(n log(n))
QuickSort
pivot
cursor low and high
swap
left>= right = new pivot
O(n log(n)) / O(n^2)
Heapsort
comparison based
2 parts
heap build out of data
remove root of heap and put in array
in place
O(n log(n))
Selection sort
sorted sublist
unsortedSublisst
find least elemt and insert
O(n^2)
Search
BFS
queue
loop
for wide trees
O(|H| + |W|)
DFS
Stack if iterative
recursive
for deep trees
O(|H| + |W|)
Binary search
sorted array
O(log(n))
graph need visited
Path
Eulerian path
A* (Astar)
Dijkstra
shortest distance
set of shortest
O(V^2)
only positive weight edges
Prim
min spanning tree
set
O(V^2)
deterministic
non deterministic
shunting yard
infix operation
Data structures
Arrays
sequential index
Linear / one dimensional
declared fixed size
Dynamic
reserved space to add
if full copy to larger
2 dimensional
Big O
Search : O(n)
Insert : O(n)
Access : O(1)
Delete : O(n)
Stacks
LIFO
Big O
Search : O(n)
Insert : O(1)
Access : O(n)
Delete : O(1)
Linked List
Double Linked List
Circular Linked List
Big O
Search : O(n)
Insert : O(1)
Access : O(n)
Delete : O(1)
Queues
FIFO
Deque
double ended queue
add remode both end
Big O
Search : O(n)
Insert : O(1)
Access : O(1)
Delete : O(1)
Big O
Delete : O(1)
Access : O(n)
Insert : O(1)
Search : O(n)
Trees
Binary trees
Binary Search Tree
no duplicate
Big O
Search : O(log(n))
Insert : O(log(n))
Access : O(log(n))
Delete : O(log(n))
n in worst case
AVL tree
height balanced BST
height diff max 1
Big O
Delete : O(log(n))
Access : O(log(n))
Insert : O(log(n))
Search : O(log(n))
Red-black Tree
node black or red
root == black
no red adjacent
Big O
Delete : O(log(n))
Access : O(log(n))
Insert : O(log(n))
Search : O(log(n))
Heaps
specialized
heap property
min
max
root == property
often binary
Tries
empty root
Big O
Search : O(n)
Insert : O(1)
Access : O(n)
Delete : O(1)
store alphabet
Graphs
vertice (node)
edge (link)
directed
undirected
Big O
Adjacency List
array of linked list
most commonly used
space O(|V| + |E|)
O(V^2)
Adjacency Matrix
0 or 1
matric / 2d array
space O(1)
O(V^2)
Edge List
array of all edges |E|
O(E)
sparce (|V|)
dense (|V|^2)
Hash Tables
key value mapping
Efficient lookup
Hashing
convert key to index
unique output
Collision
Separate chaining
Array
others
Linked List
Open addressing
Find next empty slot
Robin Hood Hashing
2-choice Hashing
2 hashing function
choose most empty
Big O
Search : O(n)
Insert : O(n)
Access : O(1) / O(n)
Delete : O(n)
order data for efficiency