Datastrukturer

Datastrukturer är sätt att organisera och lagra data för att stödja effektiva operationer i program. En datastruktur är ofta en konkret implementation av en abstrakt datatyp (ADT). Ett ADT beskriver vilka operationer som skall finnas och deras beteende, medan en datastruktur anger hur data lagras och hur operationerna genomförs.

Vanliga kategorier är linjära och icke-linjära datastrukturer. Linjära inkluderar arrayer, länkade listor, stackar och köer, där ordningen på elementen ofta är betydelsefull. Icke-linjära strukturer inkluderar träd och grafer, där relationerna mellan element kan vara mer komplexa.

Exempel på operationer är infogning, borttagning, åtkomst, traversering och sökning. Komplexiteten varierar beroende på struktur och representation. Till exempel ger direkt indexerad åtkomst i arrayer O(1) tid, medan infogning i en vanlig länkad lista ofta är O(1) men åtkomsten till mitten är O(n). Sökning i hashtabeller är i genomsnitt O(1), och i balancerade sökträd är O(log n) för insättning, borttagning och sökning. Grafer kan representeras som adjacenslistor eller adjacensmatriser.

Val av datastruktur grundar sig i användningsfall och krav på minne, tidsåtgång och om data behöver vara ordnat eller snabbt slås upp. Många programmeringsspråk erbjuder färdiga samlingstyper såsom listor, set, mappar och köer, medan andra kräver egna implementationer. Effektiv användning av datastrukturer är central i algoritmer och systemdesign.