Samenvatting · Informatica · vwo 5 Datastructuren: lijst, stack, queue, boom, graaf en dictionary

Een programma werkt met gegevens, en hoe je die organiseert bepaalt hoe makkelijk en snel je ze kunt gebruiken. Zo'n manier van organiseren heet een datastructuur. Na deze samenvatting ken je de belangrijkste datastructuren, hun operaties en wanneer je welke kiest.

Array en lijst

Een array of lijst is een rij elementen die je met een index bereikt. De index begint meestal bij 0: in [4, 8, 15, 16] is het element op index 2 gelijk aan 15.

• Een element op een bekende index lezen gaat snel, in constante tijd.
• Een element ergens in het midden invoegen of weghalen kost meer, want alle volgende elementen moeten opschuiven.
• Zoeken in een ongesorteerde lijst kost in het slechtste geval $n$ stappen.

Stack

Een stack (stapel) werkt volgens het principe LIFO: last in, first out. Het laatst toegevoegde element komt als eerste weer eruit. De operaties zijn:

• push(x): zet x bovenop de stack.
• pop(): haal het bovenste element weg en geef het terug.
• peek(): bekijk het bovenste element zonder het te verwijderen.

Toepassingen: de ongedaan maken-knop, de call stack van functieaanroepen, het controleren of haakjes in een formule goed zijn gesloten, en de terug-knop in een browser.

Queue

Een queue (wachtrij) werkt volgens het principe FIFO: first in, first out. Het eerst toegevoegde element komt eerst aan de beurt. De operaties zijn:

• enqueue(x): zet x achteraan de rij.
• dequeue(): haal het voorste element weg en geef het terug.

Toepassingen: een printerwachtrij, verzoeken die een server afhandelt, de volgorde van taken in een besturingssysteem.

Boom

Een boom is een hiërarchische structuur van knopen die met elkaar verbonden zijn. De bovenste knoop is de wortel. Een knoop heeft hoogstens één ouder en nul of meer kinderen; een knoop zonder kinderen heet een blad. De hoogte van de boom is het aantal niveaus van de wortel tot het laagste blad.

Een binaire boom heeft per knoop hoogstens twee kinderen. Een binaire zoekboom is een binaire boom waarin voor elke knoop geldt: alles in de linkerdeelboom is kleiner en alles in de rechterdeelboom is groter. Daardoor kun je net als bij binair zoeken in elke stap de helft van de boom overslaan.

In een evenwichtige binaire zoekboom met $n$ knopen duurt zoeken ongeveer ${\log }_{2}n$ stappen. Is de boom scheef (bijvoorbeeld bij het toevoegen van reeds gesorteerde data), dan degenereert hij tot een lijst en duurt zoeken $n$ stappen.

Bomen zie je ook in mappenstructuren, stambomen en de HTML-structuur van een webpagina.

Graaf

Een graaf bestaat uit knopen (punten) en kanten (verbindingen). Anders dan bij een boom mogen er kringen in zitten en kan een knoop meerdere "ouders" hebben. Kanten kunnen een richting hebben en een gewicht (bijvoorbeeld een afstand). Voorbeelden: een wegennetwerk, een sociaal netwerk, het internet. Algoritmen zoals die voor de kortste route werken op grafen.

Dictionary

Een dictionary (of map) bewaart sleutel-waardeparen. Je zoekt een waarde op via de sleutel, bijvoorbeeld een telefoonnummer op naam. Achter de schermen gebruikt een dictionary vaak een hashtabel, waarmee opzoeken gemiddeld in constante tijd gaat.

Welke kies je?

Let op

• Stack is LIFO, queue is FIFO. Wissel ze niet om.
• pop() geeft het bovenste element terug én haalt het weg; peek() haalt niets weg.
• Een boom is een speciale graaf zonder kringen met één wortel.
• Een zoekboom werkt alleen snel als hij redelijk in balans is.

In het kort

• Een lijst bereik je met een index die bij 0 begint.
• Stack is LIFO (push, pop, peek); queue is FIFO (enqueue, dequeue).
• Een binaire zoekboom heeft links kleinere en rechts grotere waarden; in-order doorlopen geeft gesorteerde data.
• Een graaf heeft knopen en kanten en mag kringen bevatten; een boom niet.
• Een dictionary zoekt een waarde op via een sleutel.