Datastruktur

En datastruktur er en måte å organisere og lagre data på slik at operasjoner som innsetting, fjerning, søk og traversering kan gjennomføres effektivt. Valget av datastruktur påvirker ytelse og minnebruk i et program, og må tilpasses hvilke operasjoner som er mest kritiske.

Datastrukturer deles ofte inn i lineære og ikke-lineære strukturer. Lineære strukturer organiserer data i en sekvens, slik at elementene har en naturlig rekkefølge, mens ikke-lineære strukturer lar relasjoner mellom elementer danne mer komplekse forbindelser, som grafer.

Vanlige datastrukturer inkluderer arrays, lenkede lister, stakker og køer, prioritetskøer, trær (som binære søketrær og B-trær) og grafer. Hashtabeller gir ofte forventet konstant tid for innsetting og oppslag.

Operasjoner som innsetting, fjerning, søk og traversering har varierende kostnader avhengig av datastrukturen. Generelt gir arrays rask direkte tilgang med O(1) ved indeks, mens innsetting og sletting i en innrettet posisjon i en array ofte krever O(n) tid. Lenke-lister har ofte lavere innsettingskostnad, men tregere tilgang, mens hashtabeller gir ofte raskt oppslag under forutsetning av en god hash-funksjon.

Valg av datastruktur avhenger av tilgjengelige operasjoner, mengden data, minnebegrensninger og behov for cache-effektivitet. I praksis realiseres ofte et abstrakt datatypens nivå med en datastruktur som passer de forventede arbeidsmønstrene.

Datastrukturer er grunnleggende byggesteiner i algoritmer og programdesign, og forståelse av deres egenskaper er sentralt for effektiv utvikling.