Datastrukturer 101: Arrays – en visuel introduktion for begyndere

Lær de datastrukturer at kende, som du bruger hver dag.

👋 Velkommen! Lad os starte med noget vigtig kontekst. Lad mig spørge dig om følgende:
✅ Hører du musik på din smartphone?
✅ Har du en liste over kontakter på din telefon?
✅ Har du nogensinde set et leaderboard under en konkurrence?

Hvis dit svar er “ja” til et af disse spørgsmål, så er det næsten sikkert, at du har brugt arrays, og du vidste det ikke engang! 😃 Arrays er meget kraftfulde datastrukturer, der gemmer lister af elementer. De har uendelige anvendelsesmuligheder. De er meget vigtige i datalogiens verden.

I denne artikel vil du lære fordelene og ulemperne ved arrays, deres struktur, operationer og anvendelsesmuligheder.

Lad os begynde! 👍

🔎 Dyb dykning i den grundlæggende struktur af arrays

For at forstå, hvordan de fungerer, er det meget nyttigt at visualisere din computers hukommelse som et gitter, ligesom det nedenfor. Hver oplysning er gemt i et af de små elementer (firkanter), der udgør gitteret.

Arrays udnytter denne “gitterstruktur” til at gemme lister med relaterede oplysninger på tilstødende hukommelsesplaceringer for at garantere ekstrem effektivitet i forbindelse med at finde disse værdier. 🔳🔳🔳🔳 🔳

Du kan tænke på arrays på denne måde:

Denes elementer ligger ved siden af hinanden i hukommelsen. Hvis du har brug for at få adgang til mere end ét af dem, er processen ekstremt optimeret, fordi computeren allerede ved, hvor værdien befinder sig.

Fedt, ikke? Lad os lære, hvordan det fungerer bag kulisserne! 😃

📚 Klassifikation

Arrays klassificeres som homogene datastrukturer, fordi de lagrer elementer af samme type.

De kan lagre tal, strenge, boolean-værdier (sandt og falsk), tegn, objekter osv. Men når du først har defineret den type værdier, som dit array skal gemme, skal alle dets elementer være af samme type. Du kan ikke “blande” forskellige datatyper.

👀 Læsning af værdier – magien begynder!

Den fantastiske styrke ved arrays kommer fra deres effektivitet i forbindelse med adgang til værdier. Dette opnås takket være dens gitterlignende struktur. Lad os se nærmere på dette.🔍

Når du opretter et array, skal du:
– Tildele det til en variabel. 👈
– Definerer den type elementer, som den skal gemme. 🎈
– Definerer dens størrelse (det maksimale antal elementer). 📚

💡 Bemærk: Det navn, som du tildeler denne variabel, er meget vigtigt, fordi du senere i din kode vil bruge den til at få adgang til værdier og til at ændre arrayet.

Men hvordan kan du fortælle computeren, hvilken bestemt værdi du gerne vil have adgang til? Det er her, at indeks spiller en afgørende rolle!

1️⃣ Indeks

Du bruger det, der kaldes et “indeks” (“indeks” i flertal), til at få adgang til en værdi i et array. Det er et tal, der henviser til den placering, hvor værdien er gemt.

Som du kan se i diagrammet nedenfor, henvises der til det første element i arrayet ved hjælp af indeks 0. Efterhånden som du bevæger dig længere mod højre, øges indekset med én for hver plads i hukommelsen.

💡 Bemærk: Jeg ved godt, at det umiddelbart virker mærkeligt at begynde at tælle fra 0 i stedet for 1, men dette kaldes nulbaseret nummerering. Det er meget almindeligt inden for datalogi.

Den generelle syntaks for at få adgang til et element er: <ArrayVariable>

For eksempel:
Hvis dit array er gemt i variablen myArray, og du vil have adgang til det første element (ved indeks 0), skal du bruge myArray

2️⃣ Hukommelse

Nu da du ved, hvordan du får adgang til værdier, skal vi se, hvordan arrays gemmes i din computers hukommelse. Når du definerer arrayets størrelse, er al denne plads i hukommelsen “reserveret” fra det øjeblik til fremtidige værdier, som du måske ønsker at indsætte.

💡 Bemærk: Hvis du ikke fylder arrayet med værdier, vil denne plads blive holdt reserveret og tom, indtil du gør det.

For eksempel:
Lad os sige, at du definerer et array af størrelse 5, men kun indsætter én værdi. Alt det resterende rum vil være tomt og “reserveret” i hukommelsen og vente på fremtidige opgaver.

Dette er vigtigt, fordi arrays er ekstremt effektive i forbindelse med adgang til værdier, fordi alle elementer gemmes i sammenhængende rum i hukommelsen. På den måde ved computeren præcis, hvor den skal kigge for at finde de ønskede oplysninger.

Men… der er en ulempe ved det 😞 fordi det ikke er hukommelseseffektivt. Du reserverer hukommelse til fremtidige operationer, som måske ikke finder sted. Derfor anbefales arrays i situationer, hvor du på forhånd ved, hvor mange elementer du vil gemme.

🔧 Operationer – bag kulisserne!

Nu da du ved, hvad arrays er, når de bruges, og hvordan de gemmer elementer, vil vi dykke ned i deres operationer som indsættelse og fjernelse.

1️⃣ Indsættelse – Velkommen!

Lad os sige, at vi har et array på størrelse 6, og at der stadig er en tom plads. Vi ønsker at indsætte et element “e” i begyndelsen af arrayet (indeks 0), men denne plads er allerede optaget af elementet “a”. Hvad skal vi gøre?

For at indsætte i arrays flytter vi alle de elementer, der befinder sig til højre for indsættelsesstedet, et indeks til højre. Element “a” vil nu være på indeks 1, element “b” vil være på indeks 2 osv…

💡 Bemærk: Du bliver nødt til at oprette en variabel for at holde styr på det sidste indeks, der indeholder elementer. I diagrammet ovenfor er arrayet fyldt op til indeks 4 før indsættelsen. På denne måde kan du afgøre, om arrayet er fuldt, og hvilket indeks du skal bruge til at indsætte et element i slutningen.

Når du har gjort dette, er vores element indsat med succes. 👏

⚠️ Vent et øjeblik! Hvad sker der, hvis arrayet er fuldt?

Hvad tror du, der vil ske, hvis arrayet er fuldt, og du forsøger at indsætte et element? 😱

I dette tilfælde skal du oprette et nyt, større array og manuelt kopiere alle elementerne ind i dette nye array. Denne operation er meget dyr, tidsmæssigt set. Forestil dig, hvad der ville ske, hvis du havde et array med millioner af elementer! Det kunne tage meget lang tid at gennemføre. ⏳

💡 Bemærk: Den eneste undtagelse fra denne regel, hvor indsættelse er meget hurtig, er, når du indsætter et element i slutningen af arrayet (ved det indeks, der er placeret til højre for det sidste element), og der stadig er plads til rådighed. Dette sker på konstant tid O(1).

2️⃣ Sletning- Bye, Bye!

Lad os nu sige, at du ønsker at slette et element fra arrayet.

For at bevare effektiviteten af tilfældig adgang (at kunne tilgå arrayet via et indeks ekstremt hurtigt) skal elementerne lagres i sammenhængende områder af hukommelsen. Du kan ikke bare slette elementet og lade pladsen stå tom.

Du skal flytte de elementer, der kommer efter det element, som du vil slette, et indeks til venstre.

Og til sidst har du dette resulterende array 👇. Som du kan se, er det lykkedes at slette “b”.

💡 Bemærk: Sletning er meget effektiv, når du fjerner det sidste element. Da du skal oprette en variabel for at holde styr på det sidste indeks, der indeholder elementer (i diagrammet ovenfor, indeks 3), kan du direkte fjerne dette element ved hjælp af indekset.

3️⃣ Finde et element

Du har tre muligheder for at finde et element i et array:

• Hvis du ved, hvor det er placeret, skal du bruge indekset.
• Hvis du ikke ved, hvor det er placeret, og dine data er sorteret, kan du bruge algoritmer til at optimere din søgning, f.eks. binær søgning.
• Hvis du ikke ved, hvor det befinder sig, og dine data ikke er sorteret, skal du søge gennem hvert element i arrayet og kontrollere, om det aktuelle element er det element, du leder efter (se sekvensen af diagrammer nedenfor).

👋 Sammenfattende…

• Arrays er ekstremt kraftfulde datastrukturer, der lagrer elementer af samme type. Elementernes type og arrayets størrelse ligger fast og er defineret, når du opretter det.
• Hukommelse allokeres straks efter, at arrayet er oprettet, og det er tomt, indtil du tildeler værdierne.
• Eelementerne er placeret på sammenhængende steder i hukommelsen, så der kan tilgås meget effektivt (tilfældig adgang, O(1) = konstant tid) ved hjælp af indekser.
• Indekser starter ved 0, ikke 1, som vi er vant til.
• Indsættelse af elementer i begyndelsen eller i midten af arrayet indebærer, at man flytter elementer til højre. Hvis arrayet er fuldt, oprettes et nyt, større array (hvilket ikke er særlig effektivt). Indsættelse i slutningen af arrayet er meget effektiv, konstant tid O(1).
• Fjernelse af elementer fra begyndelsen eller midten af arrayet indebærer flytning af alle elementer til venstre for at undgå at efterlade en tom plads i hukommelsen. Dette garanterer, at elementerne gemmes på sammenhængende pladser i hukommelsen. Det er meget effektivt at fjerne i slutningen af arrayet, fordi man kun sletter det sidste element.
• For at finde et element skal man kontrollere hele arrayet, indtil man finder det. Hvis dataene er sorteret, kan du bruge algoritmer som f.eks. binær søgning til at optimere processen.

“Lær af i går, lev for i dag, håb for i morgen. Det vigtige er ikke at holde op med at stille spørgsmål.”
– Albert Einstein

👋 Tak!

Jeg håber virkelig, at du kunne lide min artikel. ❤️
Følg mig på Twitter for at finde flere artikler som denne. 😃