Datastruktur

Datastruktur syftar inom datavetenskap på en strukturering av data på ett sådant sätt att en dator på ett effektivt sätt kan lagra och komma åt närbesläktad data. Den enklaste datastrukturen är ett endimensionellt fält, där datatyper eller adresser lagras sekventiellt i minnet och adresseras genom ett heltalsindex.^[1]

Synsätt

En abstrakt/matematisk beskrivning av en datastrukturs data och operationer betecknas abstrakt datatyp,^[2] eller abstrakt datastruktur. En sådan gränssnittsbeskrivningen är implementationsoberoende, medan en implementation av en abstrakt datatyps gränssnitt behandlar konkreta datastrukturer. Exempelvis: En stack har två operationer: push och pop. En matematisk beskrivning av dessa två operationer beskriver den abstrakta datatypen stack. För att i praktiken fungera behöver en stack implementeras, genom nyttjandet av algoritmer och konkreta datastrukturer.

Programvaruutveckling

Valet av datastruktur kan vara kritiskt för att få algoritmer att arbeta effektivt. Under utvecklandet av vissa sorters program är valet av datastrukturer primärt, eftersom erfarenhet från konstruktion av storskaliga system har visat att svårigheten att implementera och kvaliteten på det slutliga resultatet beror i hög grad på valet av datastruktur.^{[källa behövs]}. Denna insikt har gett upphov till många formaliserade designmetoder och programspråk i vilka datastrukturer, i stället för algoritmer, är nyckelfaktor. Objektorienterade programspråk som C++ och Java är en grupp av språk som visar denna filosofi.

Exempel på datastrukturer

• Linjära datastrukturer
  • Fält (alternativt uppställning)
  • Lista
    • Länkad lista
      • Skipplista
  • Hashtabell
  • Stack
  • Kö
    • Prioritetskö
  • Tvåvägskö
• datastrukturer för grafer
  • Scengraf
  • Träd
    • Binärträd
    • AVL-träd
    • B-träd
    • Parseträd
    • Röd-svart träd
    • Splayträd
    • Heap
    • String trie
    • Suffix trie
• Datatyp