Datastruktur

En datastruktur er innen informatikk en måte å organisere data på i en datamaskin. Ved behandling av store datamengder er det en nødvendighet å bruke gode datastrukturer slik at effektive algoritmer kan anvendes for å løse beregningene på kortest mulig tid. En god datastruktur kjennetegnes av at den minimerer antallet beregninger CPU-en må gjøre, samt at den minimerer bruken av minneplass og sørger for platelageret blir brukt minst mulig.

Generelt sett er det fire forskjellige grunnleggende operasjoner som må kunne gjøres i en datastruktur:

1. Sette inn et element
2. Fjerne et element
3. Søke etter et bestemt element
4. Teste om strukturen er tom

Mange programmeringsspråk inneholder ferdige moduler en programmerer kan bruke til å skape effektive datastrukturer. Disse ligger ferdige i språkets standardbibliotek, slik at de praktiske implementasjonene gjemmes for programmereren.

Typer datastrukturer

Datastrukturer kan deles inn i to hovedgrupper; lineære datastrukturer, og datastrukturer som baserer seg på grafer.

Blant de lineære datastrukturene finner man lister, herunder lenkede lister. Tabeller, hashtabeller, stakker og køer er andre viktige lineære datastrukturer.

Av datastrukturene som bygger på grafteori, er trær av forskjellige typer den viktigste. Det finnes mange typer trær, de viktigste er binære søketrær og heaper. I tillegg til trær er datastrukturen kalt disjunkte mengder viktig.