6 datastrukturer, som enhver programmør bør kende

Vejen til at blive en dygtig og succesfuld programmør er svær, men en, der bestemt er opnåelig. Datastrukturer er en kernekomponent, som enhver programmeringsstuderende skal mestre, og chancerne er, at du måske allerede har lært eller arbejdet med nogle grundlæggende datastrukturer såsom arrays eller lister.

Interviewere har en tendens til at foretrække at stille spørgsmål relateret til datastrukturer, så hvis du forbereder dig til en jobsamtale, bliver du nødt til at opfriske din viden om datastrukturer. Læs med, når vi lister de vigtigste datastrukturer for programmører og jobsamtaler.

Sammenkædede lister er en af ​​de mest basale datastrukturer og ofte udgangspunktet for studerende i de fleste datastrukturkurser. Sammenkædede lister er lineære datastrukturer, der tillader sekventiel dataadgang.

Elementer inden for den sammenkædede liste er gemt i individuelle noder, der er forbundet (linket) ved hjælp af pointere. Du kan tænke på en sammenkædet liste som en kæde af noder forbundet med hinanden via forskellige pointere.

Relaterede: En introduktion til brug af linkede lister i Java

Inden vi kommer nærmere ind på de forskellige typer af linkede lister, er det afgørende at forstå strukturen og implementeringen af ​​den enkelte node. Hver node i en sammenkædet liste har mindst én pointer (dobbeltlinkede listenoder har to pointere), der forbinder den med den næste node på listen og selve dataelementet.

Hver sammenkædet liste har en hoved- og halenode. Enkelt-linkede listeknuder har kun én pointer, der peger på den næste knude i kæden. Ud over den næste pointer har dobbeltforbundne listeknuder en anden pointer, der peger på den forrige node i kæden.

Interviewspørgsmål relateret til linkede lister drejer sig normalt om indsættelse, søgning eller sletning af et specifikt element. Indsættelse i en linket liste tager O(1) tid, men sletning og søgning kan i værste fald tage O(n) tid. Så linkede lister er ikke ideelle.

2. Binært træ

Binære træer er den mest populære delmængde af træfamiliens datastruktur; elementer i et binært træ er arrangeret i et hierarki. Andre typer træer inkluderer AVL, rød-sort, B-træer osv. Noder i det binære træ indeholder dataelementet og to pointere til hver underordnet node.

Hver overordnet node i et binært træ kan maksimalt have to underordnede knudepunkter, og hver underordnede knude kan til gengæld være en forælder til to knudepunkter.

Relaterede: En begynderguide til binære træer

Et binært søgetræ (BST) gemmer data i en sorteret rækkefølge, hvor elementer med en nøgleværdi mindre end den overordnede noden gemmes til venstre, og elementer med en nøgleværdi, der er større end den overordnede node, gemmes på ret.

Binære træer bliver ofte spurgt i interviews, så hvis du gør dig klar til et interview, bør du vide, hvordan du fladgør et binært træ, slår et specifikt element op og mere.

3. Hash tabel

Hash-tabeller eller hash-kort er en yderst effektiv datastruktur, der gemmer data i et array-format. Hvert dataelement er tildelt en unik indeksværdi i en hash-tabel, som giver mulighed for effektiv søgning og sletning.

Processen med at tildele eller kortlægge nøgler i et hash-kort kaldes hashing. Jo mere effektiv hash-funktionen er, jo bedre er effektiviteten af ​​selve hashtabellen.

Hver hash-tabel gemmer dataelementer i et værdiindeks-par.

Hvor værdi er de data, der skal lagres, og indeks er det unikke heltal, der bruges til at kortlægge elementet i tabellen. Hash-funktioner kan være meget komplekse eller meget enkle, afhængigt af den nødvendige effektivitet af hashtabellen og hvordan du vil løse kollisioner.

Kollisioner opstår ofte, når en hash-funktion producerer den samme mapping for forskellige elementer; hash map kollisioner kan løses på forskellige måder, ved hjælp af åben adressering eller kæde.

Hash-tabeller eller hash-kort har en række forskellige applikationer, herunder kryptografi. De er førstevalgsdatastrukturen, når indsættelse eller søgning i konstant O(1) tid er påkrævet.

4. Stabler

Stakke er en af ​​de mere simple datastrukturer og er ret nemme at mestre. En stakdatastruktur er i det væsentlige enhver virkelige stak (tænk på en stak kasser eller plader) og fungerer på en LIFO-måde (Last In First Out).

Stacks' LIFO-egenskab betyder, at det element, du sidst indsatte, vil blive tilgået først. Du kan ikke få adgang til elementer under det øverste element i en stak uden at poppe elementerne over det.

Stabler har to primære handlinger - push og pop. Push bruges til at indsætte et element i stakken, og pop fjerner det øverste element fra stakken.

De har også masser af nyttige applikationer, så det er meget almindeligt, at interviewere stiller spørgsmål relateret til stakke. Det er meget vigtigt at vide, hvordan man vender en stak og evaluerer udtryk.

5. Køer

Køer ligner stakke, men fungerer på en FIFO-måde (First In First Out), hvilket betyder, at du kan få adgang til de elementer, du indsatte tidligere. Kødatastrukturen kan visualiseres som en hvilken som helst kø i det virkelige liv, hvor folk placeres baseret på deres ankomstrækkefølge.

Indsættelsesoperation af en kø kaldes enqueue, og sletning/fjernelse af et element fra begyndelsen af ​​køen omtales som dequeuing.

Relaterede: En begyndervejledning til at forstå køer og prioriterede køer

Prioritetskøer er en integreret anvendelse af køer i mange vitale applikationer, såsom CPU-planlægning. I en prioritetskø er elementer ordnet efter deres prioritet frem for ankomstrækkefølgen.

6. Dynger

Dynger er en type binært træ, hvor noder er arrangeret i stigende eller faldende rækkefølge. I en Min Heap er nøgleværdien for forælderen lig med eller mindre end dens børns, og rodnoden indeholder minimumsværdien af ​​hele heapen.

På samme måde indeholder rodknuden på en Max Heap den maksimale nøgleværdi for heapen; du skal beholde min/max heap-egenskaben i hele heapen.

Relaterede: Dynger vs. Stabler: Hvad adskiller dem?

Dynger har masser af anvendelser på grund af deres meget effektive natur; primært implementeres prioritetskøer ofte gennem heaps. De er også en kernekomponent i heapsort-algoritmer.

Lær datastrukturer

Datastrukturer kan virke rystende i starten, men afsætte nok tid, og du vil finde dem nemme som en kage.

De er en vital del af programmering, og næsten alle projekter kræver, at du bruger dem. Det er vigtigt at vide, hvilken datastruktur der er ideel til et givet scenarie.

7 algoritmer, som enhver programmør bør kende

Disse algoritmer er afgørende for enhver programmørs arbejdsgang.

Læs Næste

Om forfatteren