Common Data Structure Operations
| Data Structure |
Time Complexity |
Space Complexity |
|
Average |
Worst |
Worst |
|
Access |
Search |
Insertion |
Deletion |
Access |
Search |
Insertion |
Deletion |
|
| Array |
θ(1) |
θ(n) |
θ(n) |
θ(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| Stack |
θ(n) |
θ(n) |
θ(1) |
θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Queue |
θ(n) |
θ(n) |
θ(1) |
θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Singly Linked List |
θ(n) |
θ(n) |
θ(1) |
θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Doubly Linked List |
θ(n) |
θ(n) |
θ(1) |
θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Skip List |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(nlog(n)) |
| Hash Table |
N/A |
θ(1) |
θ(1) |
θ(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| Binary Search Tree |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| Cartesian Tree |
N/A |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| B-Tree |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Red-Black Tree |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Splay Tree |
N/A |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| AVL Tree |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| KD Tree |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| Algoritdm |
Time Complexity |
Space Complexity |
|
Best |
Average |
Worst |
Worst |
| Quicksort |
Ω(nlog(n)) |
θ(nlog(n)) |
O(n^2) |
O(log(n)) |
| Mergesort |
Ω(nlog(n)) |
θ(nlog(n)) |
O(nlog(n)) |
O(n) |
| Timsort |
Ω(n) |
θ(nlog(n)) |
O(nlog(n)) |
O(n) |
| Heapsort |
Ω(nlog(n)) |
θ(nlog(n)) |
O(nlog(n)) |
O(1) |
| Bubble sort |
Ω(n) |
θ(n^2) |
O(n^2) |
O(1) |
| Insertion sort |
Ω(n) |
θ(n^2) |
O(n^2) |
O(1) |
| Selection sort |
Ω(n^2) |
θ(n^2) |
O(n^2) |
O(1) |
| Tree sort |
Ω(nlog(n)) |
θ(nlog(n)) |
O(n^2) |
O(n) |
| Shell sort |
Ω(nlog(n)) |
θ(nlog(n)^2) |
O(nlog(n)^2) |
O(1) |
| Bucket sort |
Ω(n+k) |
θ(n+k) |
O(n^2) |
O(n) |
| Radix sort |
Ω(nk) |
θ(nk) |
O(nk) |
O(n+k) |
| Counting sort |
Ω(n+k) |
θ(n+k) |
O(n+k) |
O(k) |
| Cubesort |
Ω(n) |
θ(nlog(n)) |
O(nlog(n)) |
O(n) |