Datastructuren

Datastructuren zijn georganiseerde manieren om gegevens op te slaan en te organiseren zodat bewerkingen zoals zoeken, toevoegen en verwijderen efficiënt kunnen worden uitgevoerd. Ze vormen een fundamenteel onderdeel van computerwetenschap en softwareontwikkeling, en bepalen de efficiëntie van algoritmen en programma’s.

Datastructuren worden doorgaans onderverdeeld in lineaire en niet-lineaire varianten. Lineaire datastructuren slaan elementen in een volgorde op en bieden eenvoudige iteratie. Voorbeelden zijn arrays, lijsten (enkel- en dubbel gekoppelde lijsten), stacks en queues. Arrays bieden snelle indexering maar hebben een vaste grootte; dynamische arrays kunnen groeien. Lijsten ondersteunen efficiënte invoeging en verwijdering bij nabije posities.

Niet-lineaire datastructuren slaan elementen op zonder een eenvoudige lineaire volgorde en ondersteunen complexere relaties. Voorbeelden zijn bomen (binaire zoekbomen, AVL-bomen, rode-zwartbomen), grafen en hashtabellen. Bomen faciliteren hiërarchieën en snelle zoeken op basis van ordening. Grafen modelleren knopen en verbindingen. Hashtabellen bieden gemiddelde O(1) toegang via een hash-functie, afhankelijk van het aantal botsingen.

Operaties en complexiteit: de belangrijkste bewerkingen zijn invoegen, verwijderen en zoeken. Traversals (zoals in-order, pre-order en post-order voor bomen; breadth-first en depth-first search voor grafen) worden gebruikt om alle elementen te bezoeken. Tijdcomplexiteit wordt vaak uitgedrukt in O-notation.

Toepassingen: gegevensopslag en -toegang in databases, compilatietijdoptimalisatie, geheugenbeheer, caching en netwerkrouting.