For faster navigation, this Iframe is preloading the Wikiwand page for Datastructuur.

Datastructuur

Uit Wikipedia, de vrije encyclopedie

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.

Soorten datastructuren

Er zijn minstens twee klassen van datastructuren te onderscheiden.

  1. 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.
  2. 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.

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.

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.

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 (o.a. 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.

Zie de categorie Data structures van Wikimedia Commons voor mediabestanden over dit onderwerp.
{{bottomLinkPreText}} {{bottomLinkText}}
Datastructuur
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Wikiwand 2.0 is here 🎉! We've made some exciting updates - No worries, you can always revert later on