Roadmap and cheatsheet of algorithms and data structures¶

Common Data Structure Operations¶

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Read_Look up	Search	Insertion	Deletion	Read_Look up	Search	Insertion	Deletion
Array	\(O(1)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)
Stack	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)
Queue	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)
Singly-Linked List	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)
Doubly-Linked List	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)
Skip List	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(nlog(n))\)
Hash Table	\(N/A\)	\(O(1)\)	\(O(1)\)	\(O(1)\)	\(N/A\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)
Binary Search Tree	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)
Cartesian Tree	\(N/A\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(N/A\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)
B-Tree	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(n)\)
Red-Black Tree	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(n)\)
Splay Tree	\(N/A\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(N/A\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(n)\)
AVL Tree	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(n)\)
KD Tree	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(log(n))\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(n)\)

Sorting¶

Web Analytics Made Easy -
StatCounter