datastructuureigenschappen

Datastructuureigenschappen verwijzen naar de kenmerken van een datastructuur die bepalend zijn voor hoe data wordt opgeslagen en hoe bewerkingen erop presteren. Voorbeelden zijn hoe snel data kan worden gezocht, toegevoegd of verwijderd, hoeveel geheugen nodig is, en op welke manier de data kan worden doorlopen of opgezocht.

Belangrijke eigenschappen zijn tijdcomplexiteit en ruimtecomplexiteit. Tijdcomplexiteit beschrijft de snelheid van basisoperaties zoals lookup, insertie, delete, en traversal, meestal uitgedrukt in O-notatie. Ruimtecomplexiteit geeft aan hoeveel geheugen de datastructuur in beslag neemt in relatie tot het aantal elementen. In praktijk worden ook amortized en worst-case beloop geanalyseerd.

Andere eigenschappen betreffen de structuur en het gedrag. Sommige datastructuren zijn lineair (zoals arrays en gekoppelde lijsten), andere niet-lineair (zoals bomen en grafen). Sommige zijn geordend of kennen een specifieke volgorde, anderen bieden snelle hashing voor sleutel-gebaseerde toegang. Mutabiliteit (veranderlijk vs onveranderlijk) en persistentie (oude versies blijven beschikbaar) beïnvloeden hoe datastructuren in softwarepijplijnen worden gebruikt.

Daarnaast spelen balans en hoogte (bij bomen), dynamische groei en geheugenefficiëntie een rol. De keuze van een datastructuur hangt af van de gewenste operaties en de gewenste tijd- en ruimteprestaties, met vaak duidelijke trade-offs tussen snelheid van toegang, insertie en geheugenverbruik. Bekende voorbeelden zijn arrays, gelinkte lijsten, stacks, queues, hash-tabellen, bomen, heaps en grafen.