Datastructuren organiseren data op een manier die geschikt is om snel en efficiënt met die data te kunnen werken. Er bestaan verschillende soorten datastructuren, zoals lijsten, verzamelingen, mappen, bomen, enzovoort. Afhankelijk van de situatie, de ❓ Vraag of het probleem zijn sommige datastructuren meer geschikt dan andere.

👀 Voorbeeld - Kleding

Als je kleding koopt in de winkel, dan is het handig dat die op maat, van klein naar groot, hangt. Wanneer de winkelbediende de kleding moet aanvullen kost het wel wat moeite om het nieuwe kledingstuk op de juiste plaats te hangen, bij de juiste maat, maar voor de klant is het erg aangenaam winkelen op die manier.

Wanneer je de winkel binnenstapt en wil weten of een bepaald kledingstuk aanwezig is in de winkel, dan maakt het niet uit waar dat kledingstuk hangt. Je wil vooreerst weten of het aanwezig is of niet.

Voor beide problemen is een andere datastructuur vereist.

🤔 Huh? - Waarom gebruiken we niet steeds dezelfde datastructuur?

Bij het kiezen van een geschikte datastructuur houden we rekening met de complexiteit. We maken een afweging tussen de hoeveelheid plaats die nodig is in het geheugen om de datastructuur op te slaan, en de efficiëntie waarmee we de datastructuur kunnen manipuleren. Enkele voorbeelden van manipulaties zijn het toevoegen van een element, het verwijderen van een element of het wijzigen van een element.

❗ Begrip - Complexiteit

De complexiteit van een datastructuur duidt op de mate waarin de nodige hoeveelheid tijd en ruimte toenemen naarmate de data groter wordt.

We splitsen complexiteit voor datastructuren op in tijdscomplexiteit en ruimtecomplexiteit.

Tijdscomplexiteit

Tijdscomplexiteit geeft weer hoe snel je bepaalde operaties op een datastructuur kan uitvoeren. Het kan bijvoorbeeld gewenst zijn om snel iets te kunnen opzoeken, of om snel een element te verwijderen uit de datastructuur.

👀 Voorbeeld - Autokeuring

Bij de autokeuring staat er een hele rij wagens aan te schuiven om gekeurd te worden. Olivia is een medewerkster en ze krijgt van haar bazin de opdracht om aan de auto met nummerplaat 1-ABC-123 te melden dat die de fast track mag nemen.

Olivia weet natuurlijk niet waar die auto precies staat in de rij en dus moet ze één voor één langs alle auto’s gaan om hun nummerplaat te bekijken.

Wanneer ze de auto met de juiste nummerplaat vindt, is haar opdracht geslaagd. Die auto verdwijnt uit de rij en mag naar de fast track.

Stel dat de auto met nummerplaat 1-ABC-123 de laatste is van n auto’s. Pech!

De tijdscomplexiteit van dit probleem neemt toe naarmate er meer auto’s in de rij staan: als n groter wordt, dan moet Olivia meer auto’s bekijken.

👀 Voorbeeld - Autokeuring complexiteit

We zeggen dat de complexiteit van het probleem van de autokeuring lineair toeneemt en noteren dit met O(n). Lees dit als “de complexiteit neemt toe in de grootte-orde van n”. Als er twee keer zoveel auto’s in de rij staan, moet Olivia gemiddeld gezien twee keer zoveel auto’s bekijken.

Ruimtecomplexiteit

Ruimtecomplexiteit geeft weer hoeveel plaats er in het geheugen nodig is om een bepaalde datastructuur op te slaan. Natuurlijk wil je de plaats die nodig is zo klein mogelijk houden.

🤔 Huh? - Mensen doen dat toch ook?!

Hoe minder we moeten onthouden of vanbuiten leren, hoe liever.

👀 Voorbeeld - 1 byte per geheugencel

Het geheugen van een computer is niet onbeperkt. In moderne computers kan een geheugen 1 byte opslaan per geheugencel.

❓ Vraag

Hoeveel is een byte?

Een byte kan 256 verschillende waardes bijhouden. Dat betekent dat we 1 geheugencel kunnen gebruiken om:

• Een getal tussen 0 en 255 op te slaan
• Een karakter van een string op te slaan
• Een booleaanse waarde (True, False) op te slaan

👀 Voorbeeld - Werkgeheugen van je computer

Een typische grootte voor het werkgeheugen (of RAM) van een laptop is 8 gigabyte. Laten we eens uitrekenen hoeveel geheugencellen dit zijn:

• 8 gigabyte
• 8 * 1024 megabyte
• 8 * 1024 * 1024 kilobyte
• 8 * 1024 * 1024 * 1024 byte
• 8 589 934 592 geheugencellen

🧐 Wist je dat…

…dit aantal groter is dan het aantal mensen op aarde?

🤔 Huh? - Welke datastructuur is de beste?

“De beste datastructuur” bestaat niet. Het kiezen van een geschikte datastructuur voor een probleem is vaak een afweging tussen de tijdscomplexiteit en de ruimtecomplexiteit ervan. Meer van het ene betekent vaak minder van het andere. Zo heeft een snelle datastructuur vaak meer ruimte nodig.