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