10 fælles datastrukturer forklaret med videoer + øvelser

“Dårlige programmører bekymrer sig om koden. Gode ​​programmører bekymrer sig om datastrukturer og deres forhold. ” - Linus Torvalds, skaberen af ​​Linux ** Opdatering ** Mit videokursus om algoritmer er nu live! Tjek Algorithms in Motion fra Manning Publications. Få 39% rabat på mit kursus ved at bruge koden ' 39carnes '! Eller du kan få 50% rabat på mit Deep Learning in Motion-kursus med koden ' vlcarnes2 '.

Datastrukturer er en kritisk del af softwareudvikling og et af de mest almindelige emner for spørgsmål om udviklerjobsinterview.

Den gode nyhed er, at de stort set bare er specialiserede formater til organisering og lagring af data.

Jeg vil lære dig 10 af de mest almindelige datastrukturer - lige her i denne korte artikel.

Jeg har integreret videoer, som jeg oprettede til hver af disse datastrukturer. Jeg har også linket til kodeeksempler for hver af dem, som viser, hvordan man implementerer disse i JavaScript.

Og for at give dig nogle øvelser har jeg knyttet til udfordringer fra freeCodeCamp-læseplanen.

Bemærk, at nogle af disse datastrukturer inkluderer tidskompleksitet i Big O-notation. Dette er ikke inkluderet for dem alle, da tidskompleksiteten undertiden er baseret på, hvordan den implementeres. Hvis du vil lære mere om Big O Notation, skal du tjekke min artikel om det eller denne video af Briana Marie.

Bemærk også, at selvom jeg viser, hvordan jeg implementerer disse datastrukturer i JavaScript, behøver du for de fleste af dem aldrig at implementere dem selv, medmindre du bruger et sprog på lavt niveau som C.

JavaScript (som de fleste sprog på højt niveau) har indbyggede implementeringer af mange af disse datastrukturer.

At vide, hvordan man implementerer disse datastrukturer, giver dig stadig en stor fordel i din udviklerjobsøgning og kan komme til nytte, når du prøver at skrive højtydende kode.

Tilknyttede lister

En linket liste er en af ​​de mest basale datastrukturer. Det sammenlignes ofte med en matrix, da mange andre datastrukturer kan implementeres med enten en matrix eller en sammenkædet liste. De har begge fordele og ulemper.

En sammenkædet liste består af en gruppe noder, som tilsammen repræsenterer en sekvens. Hver node indeholder to ting: de faktiske data, der gemmes (som stort set kan være enhver form for data) og en markør (eller et link) til den næste node i sekvensen. Der er også dobbeltkoblede lister, hvor hver node har en markør til både det næste element og det forrige element på listen.

De mest basale operationer på en sammenkædet liste er at føje et element til listen, slette et element fra listen og søge på listen efter et element.

Se koden for en linket liste i JavaScript her.

Sammenkædet liste tidskompleksitet

Algoritme Gennemsnit Værste tilfælde
Plads 0 (n) 0 (n)
Søg 0 (n) 0 (n)
Indsæt 0 (1) 0 (1)
Slet 0 (1) 0 (1)

freeCodeCamp udfordringer

  • Arbejd med noder på en sammenkædet liste
  • Opret en sammenkædet listeklasse
  • Fjern elementer fra en sammenkædet liste
  • Søg på en sammenkædet liste
  • Fjern elementer fra en sammenkædet liste efter indeks
  • Tilføj elementer ved et specifikt indeks på en sammenkædet liste
  • Opret en dobbeltkoblet liste
  • Vend en dobbeltkoblet liste

Stakke

En stak er en grundlæggende datastruktur, hvor du kun kan indsætte eller slette elementer øverst i stakken. Det ligner lidt en bunke. Hvis du vil se på en bog midt i stakken, skal du først fjerne alle bøgerne over den.

Stakken betragtes som LIFO (Last In First Out) - hvilket betyder at det sidste element, du lægger i stakken, er det første element, der kommer ud af stakken

Der er tre hovedoperationer, der kan udføres på stakke: indsættelse af et element i en stak (kaldet 'push'), sletning af et element fra stakken (kaldet 'pop') og visning af indholdet af stakken (undertiden kaldet 'pip ').

Se koden for en stak i JavaScript her.

Stak tidskompleksitet

Algoritme Gennemsnit Værste tilfælde
Plads 0 (n) 0 (n)
Søg 0 (n) 0 (n)
Indsæt 0 (1) 0 (1)
Slet 0 (1) 0 (1)

freeCodeCamp udfordringer

  • Lær hvordan en stak fungerer
  • Opret en stakklasse

Køer

Du kan tænke på en kø som en række mennesker i en købmand. Den første i køen er den første, der skal serveres. Ligesom en kø.

En kø betragtes som FIFO (First In First Out) for at demonstrere, hvordan den får adgang til data. Dette betyder, at når et nyt element er tilføjet, skal alle elementer, der blev tilføjet før, fjernes, før det nye element kan fjernes.

En kø har kun to hovedoperationer: enqueue og dequeue. Enqueue betyder at indsætte et element bag i køen og dequeue betyder at fjerne det forreste element.

Se koden for en kø i JavaScript her.

Køtidskompleksitet

Algoritme Gennemsnit Værste tilfælde
Plads 0 (n) 0 (n)
Søg 0 (n) 0 (n)
Indsæt 0 (1) 0 (1)
Slet 0 (1) 0 (1)

freeCodeCamp udfordringer

  • Opret en køklasse
  • Opret en prioritetskø klasse
  • Opret en cirkulær kø

Sæt

Den indstillede datastruktur gemmer værdier uden nogen bestemt rækkefølge og uden gentagne værdier. Udover at være i stand til at tilføje og fjerne elementer til et sæt, er der et par andre vigtige sætfunktioner, der fungerer med to sæt på én gang.

  • Union - Dette kombinerer alle elementerne fra to forskellige sæt og returnerer dette som et nyt sæt (uden duplikater).
  • Skæringspunkt - Givet to sæt, returnerer denne funktion et andet sæt, der har alle elementer, der er en del af begge sæt.
  • Forskel - Dette returnerer en liste over emner, der er i et sæt, men IKKE i et andet sæt.
  • Delsæt - Dette returnerer en boolsk værdi, der viser, om alle elementerne i et sæt er inkluderet i et andet sæt.

Se koden for at implementere et sæt i JavaScript her.

freeCodeCamp udfordringer

  • Opret en sæt klasse
  • Fjern fra et sæt
  • Sætets størrelse
  • Udfør en union på to sæt
  • Udfør et skæringspunkt på to datasæt
  • Udfør en forskel på to datasæt
  • Udfør en undersæt-kontrol på to datasæt
  • Opret og tilføj til sæt i ES6
  • Fjern genstande fra et sæt i ES6
  • Brug .har og .størrelse på et ES6-sæt
  • Brug Spread og Notes til integration af ES5 Set ()

Kort

Et kort er en datastruktur, der gemmer data i nøgle / værdipar, hvor hver nøgle er unik. Et kort kaldes undertiden et associerende array eller en ordbog. Det bruges ofte til hurtig opslag af data. Kort tillader følgende ting:

  • tilføjelsen af ​​et par til samlingen
  • fjernelse af et par fra samlingen
  • ændringen af ​​et eksisterende par
  • opslag af en værdi, der er knyttet til en bestemt nøgle

Se koden for at implementere et kort i JavaScript her.

freeCodeCamp udfordringer

  • Opret en kort datastruktur
  • Opret et ES6 JavaScript-kort

Hash-borde

En hash-tabel er en kort datastruktur, der indeholder nøgle / værdipar. Det bruger en hash-funktion til at beregne et indeks i en række skovle eller slots, hvorfra den ønskede værdi kan findes.

Hash-funktionen tager normalt en streng som input, og den udsender en numerisk værdi. Hash-funktionen skal altid give det samme outputnummer for den samme input. Når to indgange hash til samme numeriske output, kaldes dette en kollision. Målet er at få få kollisioner.

Så når du indtaster et nøgle / værdipar i en hash-tabel, køres nøglen gennem hash-funktionen og omdannes til et tal. Denne numeriske værdi bruges derefter som den aktuelle nøgle, som værdien er gemt af. Når du prøver at få adgang til den samme tast igen, behandler hashing-funktionen nøglen og returnerer det samme numeriske resultat. Nummeret bruges derefter til at slå den tilknyttede værdi op. Dette giver i gennemsnit meget effektiv O (1) opslagstid.

Se koden til en hash-tabel her.

Hash-kompleksitetstids tid

Algoritme Gennemsnit Værste tilfælde
Plads 0 (n) 0 (n)
Søg 0 (1) 0 (n)
Indsæt 0 (1) 0 (n)
Slet 0 (1) 0 (n)

freeCodeCamp udfordringer

  • Opret en Hash-tabel

Binært søgetræ

Et træ er en datastruktur sammensat af noder Det har følgende egenskaber:

  1. Hvert træ har en rodknude (øverst).
  2. Rodknudepunktet har nul eller flere underknudepunkter.
  3. Hver barneknude har nul eller flere underknudepunkter osv.

En binær søgning træ tilføjer disse to egenskaber:

  1. Hver knude har op til to børn.
  2. For hver node er dens venstre efterkommere mindre end den aktuelle node, hvilket er mindre end de højre efterkommere.

Binære søgetræer muliggør hurtig opslag, tilføjelse og fjernelse af genstande. Den måde, hvorpå de er indstillet, betyder, at hver sammenligning i gennemsnit giver operationerne mulighed for at springe over halvdelen af ​​træet, så hver opslag, indsættelse eller sletning tager tid, der er proportional med logaritmen for antallet af genstande, der er gemt i træet.

Se koden til et binært søgetræ i JavaScript her.

Binær søgetidskompleksitet

Algoritme Gennemsnit Værste tilfælde
Plads 0 (n) 0 (n)
Søg 0 (log n) 0 (n)
Indsæt 0 (log n) 0 (n)
Slet 0 (log n) 0 (n)

freeCodeCamp udfordringer

  • Find den mindste og maksimale værdi i et binært søgetræ
  • Føj et nyt element til et binært søgetræ
  • Kontroller, om et element er til stede i et binært søgetræ
  • Find den mindste og maksimale højde af et binært søgetræ
  • Brug dybde første søgning i et binært søgetræ
  • Brug første søgning i bredde i et binært søgetræ
  • Slet en bladknude i et binært søgetræ
  • Slet en node med et barn i et binært søgetræ
  • Slet en node med to børn i et binært søgetræ
  • Inverter et binært træ

Trie

Trie (udtalt 'prøve') eller præfiksetræ er en slags søgetræ. En trie lagrer data i trin, hvor hvert trin er en node i trien. Forsøg bruges ofte til at gemme ord til hurtig opslag, f.eks. En funktion til automatisk udfyldelse af ord.

Hver knude i en sprogtrie indeholder et bogstav i et ord. Du følger en tries grene for at stave et ord, et bogstav ad gangen. Trinene begynder at forgrene sig, når rækkefølgen af ​​bogstaverne afviger fra de andre ord i trie, eller når et ord slutter. Hver node indeholder et bogstav (data) og en boolsk, der angiver, om noden er den sidste node i et ord.

Se på billedet, så kan du danne ord. Start altid ved rodnoden øverst og arbejd ned. Trie vist her indeholder ordet kugle, flagermus, dukke, do, dork, sovesal, sende, fornemme.

Se koden til en trie i JavaScript her.

freeCodeCamp udfordringer

  • Opret et Trie-søgetræ

Binær bunke

En binær bunke er en anden type treddatastruktur. Hver knude har højst to børn. Det er også et komplet træ. Dette betyder, at alle niveauer er fuldstændigt udfyldt indtil det sidste niveau og det sidste niveau er udfyldt fra venstre mod højre.

En binær bunke kan enten være en min bunke eller en max bunke. I en maksimal bunke er nøglerne til overordnede noder altid større end eller lig med børnenes. I en min bunke er nøglerne til overordnede knudepunkter mindre end eller lig med børnenes.

Rækkefølgen mellem niveauer er vigtig, men rækkefølgen af ​​noder på samme niveau er ikke vigtig. På billedet kan du se, at det tredje niveau af min bunken har værdierne 10, 6 og 12. Disse tal er ikke i orden.

Se koden for en bunke i JavaScript her.

Binær bunke tidskompleksitet

Algoritme Gennemsnit Værste tilfælde
Plads 0 (n) 0 (n)
Søg 0 (1) 0 (log n)
Indsæt 0 (log n) 0 (log n)
Slet 0 (1) 0 (1)

freeCodeCamp udfordringer

  • Indsæt et element i en Max Heap
  • Fjern et element fra en Max Heap
  • Implementer Heap Sort med en Min Heap

Kurve

Grafer er samlinger af noder (også kaldet hjørner) og forbindelserne (kaldet kanter) mellem dem. Grafer er også kendt som netværk.

Et eksempel på grafer er et socialt netværk. Knudepunkterne er mennesker og kanterne er venskab.

Der er to hovedtyper af grafer: rettet og ikke-rettet. Ikke-dirigerede grafer er grafer uden nogen retning på kanterne mellem noder. Rettede grafer er derimod grafer med en retning i kanterne.

To almindelige måder at repræsentere en graf på er en nærhedsliste og en nærhedsmatrix.

En nærhedsliste kan repræsenteres som en liste, hvor venstre side er knudepunktet, og højre side viser alle de andre knudepunkter, den er forbundet med.

En nærhedsmatrix er et gitter med tal, hvor hver række eller kolonne repræsenterer en anden node i grafen. Ved skæringspunktet mellem en række og en kolonne er et tal, der angiver forholdet. Nuller betyder, at der ikke er nogen kant eller forhold. De betyder, at der er et forhold. Numre højere end en kan bruges til at vise forskellige vægte.

Traversalgoritmer er algoritmer til at krydse eller besøge noder i en graf. Hovedtyperne af traversalgoritmer er søgning efter bredde-første og dybde-første-søgning. En af anvendelserne er at bestemme, hvor tæt knudepunkterne er til en rodknude. Se, hvordan du implementerer bredeste-første søgning i JavaScript i videoen nedenfor.

Se koden for bredeste-første søgning på en nærhedsmatrixgraf i JavaScript.

Binær søgetidskompleksitet

Algoritme Tid
Opbevaring O (| V | + | E |)
Tilføj Vertex O (1)
Tilføj Edge O (1)
Fjern Vertex O (| V | + | E |)
Fjern Edge O (| E |)
Forespørgsel O (| V |)

freeCodeCamp udfordringer

  • Tilstødelsesliste
  • Adjacency Matrix
  • Incidensmatrix
  • Bredde-første søgning
  • Dybde-første søgning

Mere

Bogen Grokking Algorithms er den bedste bog om emnet, hvis du er ny i datastrukturer / algoritmer og ikke har en datalogisk baggrund. Det bruger letforståelige forklaringer og sjove håndtegnede illustrationer (af forfatteren, der er en ledende udvikler hos Etsy) til at forklare nogle af datastrukturer, der er omtalt i denne artikel.

Grokking Algorithms: En illustreret guide til programmører og andre nysgerrige mennesker

Resume Grokking Algorithms er en fuldt illustreret, venlig guide, der lærer dig, hvordan du anvender almindelige algoritmer til ... www.amazon.com

Eller du kan tjekke mit videokursus baseret på den bog: Algorithms in Motion fra Manning Publications. Få 39% rabat på mit kursus ved at bruge koden ' 39carnes '!