# 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