# Data Structures
Het concept van een datastructuur kunnen we herformuleren als een ‘structuur van data’. In deze context verschuift de aandacht van gegevens (een ding) naar structuur (organisatie). We richten ons niet op dingen, maar op het proces van het organiseren van dingen.
De datastructuur die we gebruiken bij webontwikkeling is afhankelijk van onze behoeften. Er zijn namelijk redelijk wat mogelijke structuren, wil je data alfabetisch ordenen, volgens datum dat de data is aangemaakt, of dat deze gewijzigd is? Opdat we een juiste keuze kunnen maken is het essentieel dat we een goed begrip hebben van JavaScript primitieven (bijvoorbeeld: String, Boolean…) en referentietypen (bijvoorbeeld: Object, Array…).
# Soorten datastructuren
Datastructuren horen nauw samen met de studie van algoritmes, dit is echter zeer complex en valt buiten het kennisgebied van een webdeveloper.
We zullen ons in dit vak richten op enkele van de meest gebruikte datastructuren als front-ender:
- Stack en queue
- Enkelvoudig gekoppelde lijst en dubbel gekoppelde lijst
- Tree
Deze gegevensstructuren dienen een specifiek maar nuttig doel bij het organiseren van gegevens. Twee van de meest gebruikte datastructuren in webontwikkeling zijn stacks en queues. Denk maar eens na over het ‘ongedaan maken’ in Word of PhotoShop, dat kan dankzij deze stack van gegevens. En bijvoorbeeld de event-lus van een webbrowser, die events verwerkt (clicks, hovers, etc.), gebruikt een queue om data te verwerken.
# Stack
Een stack is een lineaire gegevensstructuur, het organiseert gegevens in een sequentiële volgorde genaamd LIFO, Last in First Out.
Een stack zal meestal gebruik maken van een array. Je kan aan een array items toevoegen, maar ook verwijderen. In JavaScript gebruiken volgende methods.
- push(): Voeg iets toe aan het einde van een array
let cats = ['Bob'];
cats.push('Willy'); // ['Bob', 'Willy']
cats.push('Puff', 'George'); // ['Bob', 'Willy', 'Puff', 'George'
2
3
4
5
- pop(): Net het omgekeerde als push, verwijder het laatste item van een array.
let cats = ['Bob', 'Willy', 'Mini'];
cats.pop(); // ['Bob', 'Willy']
2
3
# Queue
Net zoals een Stack is een Queue of een lineaire gegevensstructuur. In tegenstelling tot een stack verwijdert een queue alleen de oudst toegevoegde gegevens. Het volgt het FIFO principe, First in, First out
- shift(): Verwijder eerste/oudste item van een array.
let cats = ['Bob', 'Willy', 'Mini'];
cats.shift(); // ['Willy', 'Mini']
2
3
Als de implementatie van deze gegevensstructuren triviaal lijkt, dan heb je het bij het rechte eind. Ze zijn namelijk niet ontworpen om overdreven ingewikkeld te zijn; ze zijn ontworpen om ons te helpen bij het organiseren van gegevens. Als je jezelf in een context bevindt met gegevens die in een sequentiële volgorde moeten worden georganiseerd, overweeg dan om een stacks of queues te gebruiken.
# Linked list
Gekoppelde lijsten kan je vergelijken met een trektocht, er zijn meerdere ‘bestemmingen’ en op iedere bestemming is er een aanwijzing om naar de volgende locatie te gaan.
const list = {
head: {
value: 6
next: {
value: 10
next: {
value: 12
next: {
value: 3
next: null
}
}
}
}
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Voordelen
- Je kan gemakkelijk een node verwijderen want ze zijn niet echt afhankelijk van elkaar. In tegenstelling tot bij arrays.
Nadelen
- Moeilijk om in te zoeken, je moet steeds van in het begin starten.
- Verbruikt meer resources dan arrays want je hebt steeds een pointer nodig naar de volgende stap
# Enkelvoudig gekoppelde lijst
Een enkelvoudig gekoppelde lijst is een datastructuur die een reeks gekoppelde knooppunten bevat. Elk knooppunt bevat op zijn beurt gegevens en een aanwijzer, die naar een ander knooppunt kunnen wijzen.
# Dubbel gekoppelde lijst
Een dubbel gelinkte lijst neemt alle functionaliteit van een enkelvoudig gekoppelde lijst en breidt deze uit voor bi-directionele verplaatsing in een lijst. We kunnen met andere woorden een gekoppelde lijst doorlopen van het eerste knooppunt in de lijst naar het laatste knooppunt in de lijst; en we kunnen van het laatste knooppunt in de lijst doorlopen naar het eerste knooppunt in de lijst.
In tegenstelling tot een enkelvoudig gekoppelde lijst, bevat een dubbel gekoppelde lijst een verwijzing naar zowel het begin van een lijst als het einde van een lijst.
# Tree
In de informatica is een tree een gegevensstructuur die hiërarchische gegevens met knooppunten simuleert. Elk knooppunt van een tree bevat zijn eigen gegevens en verwijst naar andere knooppunten.
Trees zijn een van de meest gebruikte datastructuren in webontwikkeling. De Document Object Model (DOM) is bijvoorbeeld een tree-structuur.
De terminologie van knooppunten en aanwijzers bekijken we eens met een analogie. Laten we een tree vergelijken met een organigram. Het diagram heeft een toppositie (hoofdknooppunt), zoals CEO. Rechtstreeks onder deze positie bevinden zich andere functies, zoals vice-president (VP). Om deze relatie te vertegenwoordigen, gebruiken we pijlen die van de CEO naar een VP wijzen. Een functie, zoals de CEO, is een knooppunt; de relatie die we creëren van een CEO naar een VP is een aanwijzer. Om meer relaties in ons organigram te creëren, herhalen we dit proces - we hebben een knooppunt naar een ander knooppunt.
Een tree kent twee verschillende methoden van tree traversal: Depth-First Search (DFS) en Breadth-First Search (BFS).