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
- Hashtabell
- Stack
- Kö
- Tvåvägskö
- datastrukturer för grafer
- 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).