Een datastructuur is een manier om gegevens te ordenen. Deze manier van ordenen heeft consequenties voor de efficiëntie van algoritmen die met deze gegevens werken.
Datastructuren zijn dus ordeningsprincipes. We bespreken hieronder een aantal belangrijke datastructuren: tupels, records, rijen, lijsten en bomen. Als we zulke datastructuren toepassen op concrete verzamelingen gegevens (zogenaamde elementaire datatypen) zoals getallen of letters, dan ontstaan nieuwe (samengestelde) datatypen, bijvoorbeeld: 'rij van getallen', 'lijst van bomen van letters', enzovoort. Zo kan het datatype 'woord' worden uitgedrukt als 'rij van letters'. Programmeertalen bevatten meestal een aantal elementaire datatypen en taalconstructies voor datastructuren.
Tupels
Een tupel of n-tupel is een combinatie van n gekoppelde gegevens die tezamen een betekenis hebben. Coördinaten op het aardoppervlak - lengte- en breedtegraad - vormen bijvoorbeeld een 2-tupel. Het tijdstip 12:09:10 uur, kan als volgt als een 3-tupel voorgesteld worden.
Van een tupel kun je de afzonderlijke gegevens opvragen en uit n gegevens van het juiste type een n-tupel construeren. Afhankelijk van het tupel zijn er ook andere bewerkingen mogelijk, zoals het optellen van tupels van gelijke lengte gevuld met getallen.
Records
Een record is een combinatie van een eindig aantal gegevens, net als een tupel. De velden hebben echter geen vaste volgorde, maar worden onderscheiden via hun veldnamen, bijvoorbeeld een record van drie velden met namen 'voornaam', 'achternaam' en 'email'. Een record met deze velden kan als volgt voorgesteld worden.
Rijen
Een rij is een verzameling van gegevens die een volgnummer of index hebben. Een rij heeft een vaste lengte. Elk gegeven kan door middel van zijn index aangeduid worden. Het voorbeeld hieronder is een rij van lengte 8 met volgnummers 0 t/m 7.
Lijsten
Een lijst is een serie gegevens die (afgezien van het laatste element in de lijst) steeds naar een volgend lijstelement verwijzen, zoals in onderstaande figuur te zien is.
Het aantal elementen in een lijst is willekeurig. De elementen hebben geen index, zoals dat in een rij wel het geval is.
Bomen
In een rij en een lijst is er één vaste volgorde van elementen: je kunt spreken van bijvoorbeeld een eerste, een volgende of een laatste element. Bij bomen kan één element juist verwijzen naar meer dan één andere elementen. De elementen in een boom worden knopen genoemd, en de verwijzingsrelaties takken. Elke knoop kan dus meer dan één tak hebben. Een knoop zonder inkomende takken wordt een wortel genoemd; knopen zonder uitgaande takken worden bladeren genoemd.
Bomen worden vaak gebruikt voor zoek-algoritmen. Onderstaande boom representeert bijvoorbeeld het zoeken naar een antwoord in een raadspelletje, waarbij iemand (A) een positief geheel getal onder een gegeven bovengrens in gedachten heeft en de tegenstander (B) dat getal moet raden. Bij elke raadpoging van B geeft Ainformatie: 'mijn getal is groter dan wat je geraden hebt', 'mijn getal is kleiner dan wat je geraden hebt' of 'je hebt het getal geraden'. Stel dat de bovengrens gelijk is aan 80, dan kan een algoritme voor het raadproces goed vormgegeven worden aan de hand van onderstaande boom: je begint bovenaan met raden en afhankelijk van het antwoord ('groter' of 'kleiner') kies je de linker of de rechter tak.
Efficiëntie
De efficiëntie van een datastructuur is de mate waarin het een efficiënt, dus snel, algoritme mogelijk maakt. Bij de keuze tussen rij, lijst en boom kunnen bijvoorbeeld de volgende overwegingen een rol spelen:
- Bomen lenen zich goed voor het vlot zoeken en vinden van individuele gegevens, met name als er veel gegevens zijn. Toevoegen en verwijderen van gegevens gaat moeizaam, omdat dan de hele boom geherstructureerd moet worden.
- Lijsten zijn handig als er in een algoritme vaak gegevens tussengevoegd of verwijderd moeten worden. Zoek- en vindopdrachten kosten relatief veel inspanning als het aantal gegevens groot is: de lijst moet van voor naar achteren langs gelopen worden.
- Het voordeel van het gebruik van een lijst is juist het nadeel van gebruik van een rij en omgekeerd. Als er gegevens in een rij tussengevoegd moeten worden, moet er eerst een vrije plek gemaakt worden door alle gegevens die verderop staan, een plaats op te schuiven. Bij een verwijdering moeten juist alle verder gelegen gegevens een plaats teruggeschoven worden. Daar staat tegenover dat het met behulp van de index relatief eenvoudig is een gegeven dat op een bepaalde plek staat te benaderen.
Elegantie
Evenzo kunnen we niet over elegantie van een datastructuur op zichzelf spreken - zoiets is meer van toepassing op de combinatie van oplossingsmethode (algoritme) en een bijbehorende, listig gekozen datastructuur.