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

Källor

^ ”Data structure” (på engelska). Encyclopædia Britannica. Arkiverad från originalet den 2 januari 2018. https://web.archive.org/web/20180102152326/https://www.britannica.com/technology/data-structure. Läst 26 januari 2018. ”Data structure, way in which data are stored for efficient search and retrieval. [...] The simplest data structure is the one-dimensional (linear) array, in which stored elements are numbered with consecutive integers and contents are accessed by these numbers.”
^ Bengt Nordström: datastruktur i Nationalencyklopedins (2000).

[britannica-1] ”Data structure” (på engelska). Encyclopædia Britannica. Arkiverad från originalet den 2 januari 2018. https://web.archive.org/web/20180102152326/https://www.britannica.com/technology/data-structure. Läst 26 januari 2018. ”Data structure, way in which data are stored for efficient search and retrieval. [...] The simplest data structure is the one-dimensional (linear) array, in which stored elements are numbered with consecutive integers and contents are accessed by these numbers.”

[ne-2] Bengt Nordström: datastruktur i Nationalencyklopedins (2000).

[1]

[2]