# Samenvatting Algo & Data

## Arrays & Linked Lists

Een Array is een data structuur waarbij je random access hebt.
Hierdoor kun je op elke willekeurige plek items opzoeken.

Een Linked List is een data structuur waarbij je data achter elkaar zet.
Als je hier data wilt opzoeken zul je door de hele lijst heen moeten gaan.

Het voordeel van een linked list ten opzicht van de array is dat insetion en deletion sneller verloopt.

### Array:
|Index|0|1|2|3|4|5|6|
|-----|-|-|-|-|-|-|-|
|Value|

#### Array bigO:
|Access|Search|Insetion|Deletion|
|------|------|--------|--------|
|O(1) |O(n) | O(n) |O(n) |
De reden dat insetion en deltion n en niet 1 is na dat een element is toegevoegt moet de overige elementen verplaats worden. n is the worst case.
### Linked List:

#### Linked list bigO:
|Access|Search|Insetion|Deletion|
|------|------|--------|--------|
|O(n) |O(n) |O(1) |O(1) |

De rede dat acces en search n is en niet 1 is omdat de gehele lijst moet worden doorgelopen. In de worst case is de waarde die gevonden moet worden aan het einde van de linked list.

## Stack & Heap(memory):

Data op de stack is data die daar tijdelijk op wordt gezet. Nadat de functie voorbij is wordt deze data verwijderd. Dit is dus een "short-lived memory"

Om data op de heap op te slaan zal memory moeten worden toegewezen (door middel van een allocation functie, malloc).
De volgende code allocates 1 megabyte aan memory. Het adres wordt dan opgeslapen in de variabele ptr.

double *ptr;
ptr = malloc(1024 * 1024);

Zodra je de allocated memory niet meer gebruikt zul je deze moeten vrij maken met de "free()" functie.

## Sorting

Data kun je op meerdere manieren sorteren. Zodra data gesorteerd is kun je veel makkelijker iets opzoeken. Vaak wil je data ook gesorteerd toevoegen aan je datastructuur.

Selection sort is bijvoorbeeld een erg inefficiente manier van sorteren:
*Selection Sort proces*

Dit komt omdat je door de hele list gaat om de kleinste waarde te zoeken en deze dan omwisselt met de voorste. Daarna ga je opnieuw door de lijst heen en zoek je naar de dan laagste waarde en die wissel je dan om met de tweede plek, enzovoort. dit totdat je de hele lijst hebt gehad.
De time complexity hiervan is: O(n^2)

Merge sort is de best mogelijke manier van sorteren:
*Merge Sort Proces*

Hier worden alle getallen opgesplitst in paren en dan per paar gesorteerd. Zodra je dan twee gesorteerde paren moet sorteren hoeft de computer alleen telkens de voorste van de paren te vergelijken. Dit gaat dan zo verder totdat alles gesorteerd is.
De time complexity hiervan is: O(n*log(n))

## Stacks & Queues

### Stacks
Stacks is een datatype waar als het ware elementen op elkaar worden gestacked. Een stack heeft altijd een LIFO (Last In First Out). De het element te puchen worden elementen toegevoeg aan de aan de stack. Door de peeken worden het laatste toegevoegte element uitgelezen van de stack. Bij een pop wordt deze waarde ook van de stack afgehaald
*Stack proces*

#### Stack BigO:
|Access|Search|Insertion|Deletion|
|------|------|---------|--------|
|O(n) |O(n) |O(1) |O(1) |

### Queue
Queue is een datatype waar de eerste of de laatse toegevoegte waarde in de rij kan worden verwijdert. Bij deze datatype is er een sprake van zowel FIFO(fist in first out) als LIFO(Last in First Out).
*Queue process. Ook gespiegeld toe te passen*

#### Queue BigO:
|Access|Search|Insetion|Deletion|
|------|------|--------|--------|
|O(n) |O(n) | O(1) | O(1) |

## Sets(nog niet af)

Items zijn vaak gesorteerd in sets op basis van een eigenschap. Auto's kunnen bijvoorbeeld gesorteerd worden op prijs, merk of kleur. Het zoeken op basis van deze eigenschappen wordt "membership testing"

### Binary search
Dit is manier van zoeken wat wordt gebruikt bij een sorted array.
De array wordt telkens opgesplitst en er wordt dan gekeken of de te zoeken waarde groter of kleiner is dan deze middelste waarde. Hierdoor wordt de array telkens in tweeën gesplitst.
De time complexity hiervan is: O(log(n))

Sets is nog niet af!!!!!!!!!!!!!!!!!!!!!

## Voordelen & Nadelen typen structuren

### (Sorted) Arrays
#### *Voordelen*:
1. Directe access indien index bekend.
2. makkelijk te gebruiken.
3. Sorted is snel m.b.t. zoeken (Zie Binary Search).
#### *Nadelen*:
1. Unsorted is langzaam wat befreft zoeken. Worst case moet elke waarde worden ge-iterate.

### Linked Lists
#### *Voordelen*:
1. Makkelijk in gebruik waar hele lijst voor nodig is.
#### *Nadelen*:
1. Langzaam wat betreft zoeken. Worst case moet elke waarde worden ge-iterate.
2. 2 pointers per 'node' voor verwijzing voorliggende en achterliggende node.

### Stacks
#### *Voordelen*
1. LIFO
#### *Nadelen*
1. Data verborgen onder is onbereikbaar.

### Queues
#### *Voordelen*
1. LIFO en FIFO
#### *Nadelen*
1. Data verborgen midden in is onbereikbaar.

### Self Balancing Binary Trees
#### *Voordelen*
1. Het principe is al gesorteerd
2. Binary Search toepasbaar
#### *Nadelen*
1. 2 extra values per node voor self balancing feature

### Heaps
**T.B.D.**
### Priority Queues
**T.B.D.**

## Big O Notaties
|Structuur|Access|Search|Insert|Delete|
|---------|------|------|------|------|
|Sorted Dynamic Array|O(1)|O(n)|O(n)|O(n) |
|Linked List|O(n)|O(n) |O(1) |O(1) |
|Stack |O(n) |O(n) |O(1) |O(1) |
|Queue |O(n) |O(n) |O(1) |O(1) |
|Self Balancing Tree|O(n)|O(n)|O(n)|O(n)|
|Heap | | | | |
|Priority Tree| | | | |

|Algoritme |Worst Case |
|------------------|----------------|
|Selection Sort |O(n²)|
|Merge Sort |O(n * Log(n)) |
|Binary Search |O(Log(n)) |