Datastrukturer 101: Arrays - En visuel introduktion til begyndere

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

? Velkommen! Lad os starte med en vital kontekst. Lad mig spørge dig om dette:

✅ Lytter du til musik på din smartphone?

Keep Har du en liste over kontakter på din telefon?

✅ Har du nogensinde set et leaderboard under en konkurrence?

Hvis dit svar er “ja” på et af disse spørgsmål, er det næsten sikkert, at du har brugt arrays, og at du ikke engang vidste det! ? Arrays er meget kraftige datastrukturer, der gemmer lister over elementer. De har uendelige applikationer. De er meget vigtige i computervidenskabens verden.

I denne artikel lærer du fordele og ulemper ved arrays, deres struktur, operationer og brugssager.

Lad os begynde! ?

? Dyb dybt ned 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 den nedenfor. Hvert stykke information gemmes i et af de små elementer (firkanter), der danner gitteret.

Arrays udnytter denne "gitter" -struktur til at gemme lister med relateret information i tilstødende hukommelsessteder for at garantere ekstrem effektivitet til at finde disse værdier. ????

Du kan tænke på arrays som denne:

Deres elementer er ved siden af ​​hinanden i hukommelsen. Hvis du har brug for adgang til mere end en af ​​dem, er processen ekstremt optimeret, fordi din computer allerede ved, hvor værdien er placeret.

Fantastisk, ikke? Lad os lære, hvordan dette fungerer bag kulisserne! ?

? Klassificering

Arrays er klassificeret som homogene datastrukturer, fordi degemme elementer af samme type .

De kan gemme numre, strenge, boolske værdier (sandt og falsk), tegn, objekter osv. Men når du først har defineret den type værdier, som din matrix vil gemme, skal alle dens elementer være af den samme type. Du kan ikke "blande" forskellige typer data.

? Læsning af værdier - magien begynder!

Arrays fantastiske magt kommer fra deres effektivitet til adgangsværdier . Dette opnås takket være dets gitterlignende struktur. Lad os se nærmere på dette. ?

Når du opretter en matrix, skal du:

- Tildel den til en variabel. ?

- Definer typen af ​​elementer, som den vil gemme. ?

- Definer dens størrelse (det maksimale antal elementer). ?

? Bemærk: Det navn, du tildeler denne variabel, er meget vigtigt, fordi du vil bruge det senere i din kode 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 indekser spiller en vigtig rolle!

1️⃣ Indeks

Du bruger det, der kaldes et "indeks" ("indekser" i flertal) for at få adgang til en værdi i en matrix. Dette er et tal, der refererer til det sted, hvor værdien er gemt.

Som du kan se i diagrammet nedenfor henvises til det første element i arrayet ved hjælp af indeks 0. Når du bevæger dig længere mod højre, stiger indekset med et for hvert mellemrum i hukommelsen.

? Bemærk: Jeg ved, at det først virker underligt at begynde at tælle fra 0 i stedet for 1, men dette kaldes Zero-Based Numbering. Det er meget almindeligt inden for datalogi.

Den generelle syntaks for at få adgang til et element er:[]

For eksempel:

Hvis din matrix er gemt i variablen, myArrayog du vil have adgang til det første element (ved indeks 0), vil du brugemyArray[0]

2️⃣ Hukommelse

Nu hvor 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, "reserveres" al denne plads i hukommelsen fra det øjeblik til fremtidige værdier, som du måske vil indsætte.

? Bemærk: Hvis du ikke udfylder arrayet med værdier, holdes pladsen reserveret og tom, indtil du gør det.

For eksempel:

Lad os sige, at du definerer en matrix af størrelse 5, men kun indsætter en værdi. Al den resterende plads vil være tom og "reserveret" i hukommelsen og vente på fremtidige opgaver.

Dette er nøglen, fordi arrays er ekstremt effektive til at få adgang til værdier, fordi alle elementerne er gemt i sammenhængende rum i hukommelsen. På denne måde ved computeren nøjagtigt, hvor den skal lede for at finde de oplysninger, du har anmodet om.

Men ... der er en ulempe ved det ? fordi dette ikke er hukommelseseffektivt . Du reserverer hukommelse til fremtidige operationer, der muligvis ikke forekommer. Derfor anbefales arrays i situationer, hvor du på forhånd ved, hvor mange elementer du skal gemme.

? Operationer - bag kulisserne!

Nu hvor 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 en matrix af størrelse 6, og at der stadig er et tomt rum. Vi ønsker at indsætte et element "e" i begyndelsen af ​​arrayet (indeks 0), men dette sted er allerede taget af elementet "a." Hvad skal vi gøre?

For at indsætte i arrays flytter vi alle elementerne placeret til højre for indsættelsesstedet, et indeks til højre. Element “a” vil nu være i indeks 1, element “b” vil være på indeks 2 og så videre ...

? Bemærk: Du skal oprette en variabel for at holde styr på det sidste indeks, der indeholder elementer. I diagrammet ovenfor udfyldes arrayet op til indeks 4 før indsættelsen. På denne måde kan du bestemme, om matrixen er fuld, og hvilket indeks du skal bruge til at indsætte et element i slutningen.

Efter at have gjort dette, er vores element med succes indsat. ?

Vent et øjeblik! Hvad sker der, hvis matrixen er fuld?

Hvad tror du vil ske, hvis matrixen er fuld, og du prøver at indsætte et element? ?

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

? Bemærk: Den eneste undtagelse fra denne regel, når indsættelsen er meget hurtig, er når du indsætter et element i slutningen af arrayet (i indekset til højre for det sidste element), og der stadig er plads til rådighed. Dette gøres i konstant tid O (1).

2️⃣ Sletning - Farvel, farvel!

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

For at opretholde effektiviteten af ​​tilfældig adgang (at være i stand til at få adgang til arrayet gennem et indeks ekstremt hurtigt) skal elementerne lagres i sammenhængende hukommelsesrum. Du kan ikke bare slette elementet og lade dette rum være tomt.

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

Og endelig har du dette resulterende array ?. Som du kan se, er “b” blevet slettet.

? 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 fjerne elementet direkte ved hjælp af indekset.

3️⃣ Find et element

Du har tre muligheder for at finde et element i en matrix:

  • Hvis du ved, hvor det er placeret , skal du bruge indekset.
  • Hvis du ikke ved, hvor de 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 de er placeret, og dine data ikke sorteres , skal du søge gennem hvert element i arrayet og kontrollere, om det aktuelle element er det element, du leder efter (se rækkefølgen af ​​diagrammer nedenfor).

? Sammenfattende ...

  • Arrays er ekstremt kraftige datastrukturer, der gemmer elementer af samme type. Elementtypen og arrayets størrelse er faste og definerede, når du opretter det.
  • Hukommelse tildeles straks efter at arrayet er oprettet, og det er tomt, indtil du tildeler værdierne.
  • Deres elementer er placeret sammenhængende i hukommelsen , så de kan tilgås meget effektivt (tilfældig adgang, O (1) = konstant tid) ved hjælp af indekser .
  • Indeks starter ved 0 , ikke 1, som vi er vant til.
  • Indsættelse af elementer i begyndelsen eller i midten af ​​arrayet indebærer at flytte elementer til højre. Hvis matrixen er fuld, oprettes et nyt, større array (som ikke er særlig effektiv). Indsættelse i slutningen af ​​arrayet er meget effektiv, konstant tid O (1).
  • Fjernelse af elementer fra begyndelsen eller fra midten af ​​arrayet indebærer at flytte alle elementerne til venstre for at undgå at efterlade et tomt rum i hukommelsen. Dette garanterer, at elementerne lagres i sammenhængende rum i hukommelsen. Fjernelse i slutningen af ​​arrayet er meget effektiv, fordi du kun sletter det sidste element.
  • For at finde et element skal du kontrollere hele arrayet, indtil du finder det. Hvis dataene sorteres, kan du bruge algoritmer som binær søgning til at optimere processen.
"Lær fra i går, lev for i dag, håb for i morgen. Det vigtige er ikke at stoppe spørgsmålstegn. ”

- 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. ?