Fundamental Implementations Study Guide
=======================================

:::warning
[< Return to Home Page](https://hackmd.io/@siansiansu/HknJJm0W0)
:::

Data Structures
---------------

### Linear Data Structures

Structures that store data elements sequentially.

- Array
- [Linked List](https://hackmd.io/@siansiansu/SJIq6MPzC)
- Stack
- [Queue](https://hackmd.io/@siansiansu/S1s7IdmVA)

### Non-linear Data Structures

Structures that store data in a hierarchical or networked manner.

- Tree
- Graph

### Hash-based Data Structures

Structures that use hash functions for efficient data storage and retrieval.

- HashMap
- [HashSet](https://hackmd.io/@siansiansu/r16nazVN0)

Algorithms
----------

### Search Algorithms

Algorithms for finding specific elements in a data structure.

- [Linear Search](https://hackmd.io/@siansiansu/r1k-B5SVA)
- [Binary Search](https://hackmd.io/@siansiansu/HkpNS9HER)
- Fibonacci Search
- Interpolation Search
- Exponential Search

### Sorting Algorithms

Algorithms for arranging elements in a specific order.

- [Bubble Sort](https://hackmd.io/@siansiansu/S1mrVcrEA)
- [Insertion Sort](https://hackmd.io/@siansiansu/BJs14crNR)
- Selection Sort
- [Merge Sort](https://hackmd.io/@siansiansu/S1yFVqBVA)
- [Quick Sort](https://hackmd.io/@siansiansu/HkLu75SVR)
- Heap Sort
- Radix Sort
- Counting Sort
- Bucket Sort
- Shell Sort

Time Complexity Tables
----------------------

### Search Algorithms

| Algorithm | Best Case | Average Case | Worst Case |
| -------------------- | --------- | ------------ | ---------- |
| Linear Search | O(1) | O(n) | O(n) |
| Binary Search | O(1) | O(log n) | O(log n) |
| Fibonacci Search | - | - | - |
| Interpolation Search | - | - | - |
| Exponential Search | - | - | - |

### Sorting Algorithms

| Algorithm | Best Case | Average Case | Worst Case |
| -------------- | ---------- | ------------ | ---------- |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) |

Additional Resources
--------------------

- [Visualgo - Visualising Data Structures and Algorithms](https://visualgo.net/en)
- [Big-O Cheat Sheet](https://www.bigocheatsheet.com/)
- [GeeksforGeeks - Data Structures](https://www.geeksforgeeks.org/data-structures/)
- [Introduction to Algorithms (CLRS Book)](https://mitpress.mit.edu/books/introduction-algorithms-third-edition)