I dette blogindlæg introducerer vi konceptet datastruktur og forklarer, hvorfor arrays og linkede lister er vigtige på en letforståelig måde.
Der er gået lang tid, siden personlige computere først dukkede op i verden. Dengang var det nok at have blot én computer i huset, men i dag fungerer ikke kun computere, men også smartphones, tablets og endda husholdningsapparater som computere. Denne ændring skyldes ikke blot en stigning i antallet af enheder, men også den dramatiske udvikling i ydeevnen og funktionaliteten af hver enhed. Med tiden er hukommelsesmediernes kapacitet blevet uforlignelig i forhold til, hvad den var i de tidlige dage, og behandlingshastighederne er blevet ufatteligt hurtige. Moores lov, som er en lov, der forklarer denne ydeevneforbedring, siger, at hardwareintegrationen fordobles, og ydeevnen fordobles hver 18. måned. Denne lov har spillet en vigtig rolle i at forudsige udviklingen af halvlederindustrien, og som et resultat er hastigheden af hardwareydeevneforbedringen fortsat vokset med en bemærkelsesværdig hastighed. I overensstemmelse med denne lov er hukommelseskapaciteten på personlige computere, som tidligere var mindre end 10 MB, blevet så stor, at terabyte nu er almindelige. Dagens computere er i stand til nemt at lagre og behandle hundredvis af gigabyte data, et niveau af fremskridt som forskere tidligere ikke kunne have forestillet sig. Efterhånden som hukommelsesenheder bliver større, er det nødvendigt at overveje, hvordan man bruger dem effektivt. Metoden til at bruge hukommelsesenheder effektivt kaldes datastruktur.
For at forstå datastrukturen og dens nødvendighed er det først nødvendigt at forstå strukturen af hukommelsesenheder. En hukommelsesenhed består af et sæt små hukommelsesenheder, der kan fungere uafhængigt. Dette kan sammenlignes med et sæt små skabe med serienumre. Hvert skab kan lagre en lille mængde information, såsom et par bogstaver i alfabetet eller et par tal, og en gruppe af disse skabe udgør den samlede hukommelsesplads. Når hvert skab er tildelt et unikt nummer, kan det refereres til med dette nummer. Brugere behøver kun at huske, hvilket skab deres oplysninger er i, og de kan hente eller ændre de ønskede oplysninger uden at skulle søge gennem alle de andre skabe. At forstå denne struktur er det første skridt i at erkende vigtigheden af datastrukturer.
Behovet for datastrukturer opstår, når hukommelsesenheder opdeles i små enheder. Da størrelsen på skabe ikke er uendelig, vil ét skab ikke være nok, hvis den information, du vil gemme, er stor. For eksempel ville det være umuligt at gemme en liste over alle undervisere i naturvidenskab og teknologi i et enkelt skab med kun et par bogstaver. I sådanne tilfælde skal informationen opdeles i mindre dele og opbevares i flere skabe. Når man bruger flere skabe, ville det være meget mere effektivt kun at huske et eller to serienumre, så man kan finde alle de skabe, man har brugt, i stedet for at vælge tilfældigt tomme skabe og huske serienumrene på alle skabene. For effektivt at kunne administrere og behandle så kompleks information er det vigtigt at vælge en passende datastruktur. En god datastruktur er nødvendig for effektivt at kunne bruge flere skabe. Talrige datastrukturer er blevet udviklet gennem omfattende forskning, og blandt dem er de to mest grundlæggende strukturer arrays og linkede lister.
Et array er en struktur, der kun bruger skabe med fortløbende numre, når man bruger flere skabe. I denne struktur kan man finde alle de skabe, man har brugt, ved kun at huske nummeret på det første skab og hvor mange skabe man har brugt. Antag, at en bruger har brugt 10 skabe, og at det første skab er nummer 2016. Så kan vi straks vide, at brugeren har brugt skabene 2016, 2017, 2018, ..., 2024 og 2025. Denne struktur kræver kun, at den første position og længde huskes, så der er meget lidt yderligere information at huske, ingen spildplads og god pladsudnyttelse, og man kan straks vide, hvilket skab brugeren bruger. For eksempel kan man i det foregående eksempel straks beregne, at det femte skab, som brugeren bruger, er skabsnummer 2016 + 4 = 2020. Denne fordel ved arraystrukturen er især nyttig, når dataene ikke optager meget plads. Hvis du vil slette information midt i de brugte skabe, skal du flytte alle skabene bagefter frem et efter et, hvilket reducerer effektiviteten af sletning af information betydeligt. Selv hvis der er nok ekstra skabe, kan du ikke bruge al den resterende plads, hvis de ikke støder op til hinanden.
En linket liste er også en struktur, der kan bruges, når du vil bruge flere skabe. I modsætning til et array bruger en linket liste ikke fortløbende skabe, men gemmer i stedet nummeret på det næste skabe i hvert skabe. På denne måde kan du se alle de skabe, du har brugt, i rækkefølge, hvis du kender nummeret på det første skabe. Antag, at en bruger brugte skabene 100, 201, 43 og 1 i den rækkefølge. Så indeholder skabet 100 det første informationsstykke og 201, skabet 201 indeholder det andet informationsstykke og 43, og skabet 43 indeholder det tredje informationsstykke og 1. Denne egenskab ved linkede lister er især nyttig, når data skal behandles dynamisk. Fordelen ved denne struktur er, at så længe der er nok ledige skabe, kan al information gemmes, og i modsætning til arrays kan information i midten effektivt slettes, når det er nødvendigt. Antag, at brugeren ønsker at slette oplysningerne i felt 43. Alt, hvad de skal gøre, er at åbne felt 201 og ændre 43 til 1. Denne fleksibilitet gør sammenkædede lister meget nyttige til håndtering af variable data. Ulempen ved denne struktur er dog, at den spilder plads, fordi hvert skab kræver et ekstra nummer, der skal gemmes, og i modsætning til arrays er det ikke muligt at finde placeringen af et skab med det samme, så du skal søge gennem alle skabene fra starten, hvilket er ineffektivt.
Datastrukturer er fundamentet for mange områder inden for datalogi og er tæt forbundet med mange problemer i den virkelige verden. Faktisk er teorier som maskinlæring og big data, der i øjeblikket vinder popularitet, teorier, der beskæftiger sig med enorme mængder data, og disse teorier kan kun eksistere, hvis der findes gode datastrukturer, der kan håndtere store data. Som sådan går datastrukturer ud over simple teoretiske begreber og er fundamentet for den teknologi, vi bruger hver dag. Arrays og linkede lister er de mest grundlæggende datastrukturer og danner grundlag for næsten alle andre datastrukturer. Forståelse af disse to grundlæggende datastrukturer er afgørende for at håndtere komplekse datastrukturer. Det er nødvendigt at forstå disse teorier præcist fra bunden, så du fleksibelt kan vælge den passende datastruktur til situationen og administrere data. Ved at studere karakteristika og anvendelser af forskellige datastrukturer i dybden vil vi desuden være i stand til at løse mere komplekse og forskelligartede databehandlingsproblemer.
