# Java Algorithms & Data Structures

# ☕ Data Structures & Algorithms Implemented in Java 16

## Data Structures

- Stack
- Queue
- Priority Queue
- Dynamic Arrays
- LinkedLists
- List Comparison
- Hash Tables / HashMaps
- Graphs
- Adjacency Lists
- Binary Search Tree

## Algorithms

- Linear Search
- Binary Search
- Recursion
- Interpolation Search
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Quick Sort
- Depth First Search
- Breadth First Search
- Tree Traversal + Notes

## Notes

The course content and lessons followed can be found here.

### Definitions

**Data Structure** - `A named location that can be used to store and organize data`

**Algorithm** - `A collection of steps to solve a problem`

### Big O Notation

**BigO Notation** - `How code slows as data grows.`

- Describes the performance of an algorithm as the amount of data increases
- Machine independent (# of steps to completion)
- Ignore smaller operations (O(n + 1) -> O(n)

*Examples:*

```
n = "ammount of data";
O(1) = performance stays the same as data increases
O(n) = performance scales linearly as with data size change e.g. Linear search (single for loop)
O(log n) = performace scales logarithmicly with data size change
O(n^2) = performance scales exponentially with power 2
```

O(n)

```
class Example {
public int addUp(int n) {
int sum = 0;
for (int i = 0; i<= n; i++) {
sum += i;
}
}
}
```

O(1)

```
class Example {
public int addUp(int n) {
int sum = n * (n + 1) / 2;
return sum;
}
}
```

**Examples for common Big O**

`O(1)`

= constant time- random access of array element
- inserting at beginning of list

`O(log n)`

= logarithmic time- binary search

`O(n)`

= linear time- looping through array elements
- single for loop

`O(n log n )`

= quasilinear time- quicksort
- mergesort
- heapsort

`O(n^2)`

= quadratic time- insertion sort
- selection sort
- bubblesort

`O(!n)`

= factorial time- TSP