Datastructuur
Een datastructuur is in de informatica een manier waarop de elementen (in dit verband ook wel componenten, delen of items genoemd) van een samengestelde variabele samenhangen. De structuur bepaalt de wijze waarop de elementen selecteerbaar zijn, en daarmee op welke wijze en met welke mate van efficiëntie gegevens kunnen worden opgeslagen, gewijzigd en teruggevonden. Verder kunnen datastructuren worden gecombineerd tot complexere datastructuren.
Inhoud |
[bewerk] Soorten datastructuren
Er zijn minstens twee klassen van datastructuren te onderscheiden.
- Record Een samenstelling van velden die met een unieke naam aangesproken kunnen worden. Voorbeelden hiervan zijn records in Pascal en structs in C. Deze records worden al gedefinieerd tijdens het schrijven van het programma.
- Container Een container is een datastructuur die een variabel aantal objecten bevat. De manier waarop toegang tot deze objecten kan worden verkregen verschilt per type container.
Sommige moderne scripttalen, zoals Javascript, Python, Perl of Ruby, gebruiken het eerste soort niet meer ten gunste van andere constructies zoals een associatieve array. Dit heeft alles te maken met het feit dat computers sneller worden, en het statische record probleemloos vervangen kan worden door een dynamische constructie. Vroeger zou dit de machine onnodig vertraagd hebben en onnodig geheugen verkwisten. Dat wil overigens niet zeggen dat deze oplossingen bij voorbaat beter zijn.
[bewerk] Container
Containers kunnen op minstens één manier in twee groepen worden verdeeld. Namelijk de conceptuele containers (een abstracte datastructuur), en de implementaties van deze concepten. Het onderscheid tussen deze twee groepen is niet in alle gevallen even duidelijk omdat sommige concepten maar 1 implementatie kennen. In deze gevallen zijn de twee begrippen synoniem.
[bewerk] Concept
Voorbeelden van abstracte containers zijn:
- Array — Snelle toegang via een nummer. Grootte staat vooraf vast, resizen is duur. Een tweedimensionale array (toegang via twee nummers) heet een matrix.
- List — Toegang alleen via vorig of volgend element. Invoegen of weghalen is goedkoop.
- Queue (of wachtrij of fifo) — Alleen toegang tot het element dat er het eerst aan toegevoegd is.
- Stack (of lifo) — Alleen toegang tot het element dat er het laatst aan toegevoegd is.
- Associatieve array (of dictionary of map) — Elementen kunnen worden gezocht op een unieke sleutel. Dit lijkt op een woordenboek, vandaar de naam dictionary. Toegang tot een element is meestal redelijk snel, maar veel langzamer dan bij een array. Verwijderen is meestal goedkoop. Toevoegen iets duurder, maar wel redelijk. Dit alles hangt af van de gekozen implementatie.
- Verzameling (of set, eng.) — Bevat alleen unieke zoeksleutels.
- Bag — Bevat niet-unieke zoeksleutels.
[bewerk] Implementatie
Voorbeelden van implementaties van containers zijn o.a.
- Array — Wordt gebruikt voor de implementatie van array, queue, stack. Een bitarray wordt ook wel gebruikt voor de implementatie van verzameling, maar deze heeft beperkingen ten opzichte van de andere implementaties.
- Boomstructuur (oa heap) — Wordt gebruikt voor de implementatie van associatief array, list, verzameling, bag.
- Hashtable — Wordt gebruikt voor de implementatie van een associatieve array, list, verzameling en bag. De toegang is bijna zo snel als een array, maar hier moet (net als bij een array) van tijd tot tijd een dure resize gedaan worden.
- Linked list (unidirectioneel, bidirectioneel) — Wordt gebruikt voor de implementatie van list, queue en stack.
Alle containers kunnen met behulp van een iterator worden doorlopen.
