10 kopīgas datu struktūras, kas izskaidrotas ar videoklipiem + vingrinājumi

“Slikti programmētāji uztraucas par kodu. Labi programmētāji uztraucas par datu struktūrām un to attiecībām. ” - Linuss Torvalds, Linux ** Update veidotājs ** Mans video kurss par algoritmiem tagad ir tiešraidē! Iepazīstieties ar algoritmiem kustībā no Manning Publications. Iegūstiet 39% atlaidi no mana kursa, izmantojot kodu ' 39carnes '! Vai arī jūs varat saņemt 50% atlaidi manam Deep Learning in Motion kursam ar kodu ' vlcarnes2 '.

Datu struktūras ir kritiska programmatūras izstrādes sastāvdaļa un viena no visbiežāk sastopamajām tēmām izstrādātāja darba interviju jautājumiem.

Labā ziņa ir tā, ka tie būtībā ir tikai specializēti formāti datu organizēšanai un glabāšanai.

Es iemācīšu jums 10 visizplatītākās datu struktūras - šeit, šajā īsajā rakstā.

Esmu ievietojis videoklipus, kurus izveidoju katrai no šīm datu struktūrām. Esmu saistījis arī kodu piemērus katram no tiem, kas parāda, kā tos ieviest JavaScript.

Un, lai sniegtu jums zināmu praksi, es esmu saistīts ar izaicinājumiem no freeCodeCamp mācību programmas.

Ņemiet vērā, ka dažas no šīm datu struktūrām ietver laika sarežģītību Big O notācijā. Tas nav iekļauts visās no tām, jo ​​laika sarežģītība dažreiz ir atkarīga no tā, kā tā tiek īstenota. Ja vēlaties uzzināt vairāk par Big O Notation, skatiet manu rakstu par to vai šo Briana Marie videoklipu.

Ņemiet vērā arī to, ka, lai arī es parādīju, kā šīs datu struktūras ieviest JavaScript, lielākajai daļai no tām jums nekad nevajadzēs tās ieviest pašiem, ja vien jūs neizmantojāt tādu zema līmeņa valodu kā C.

JavaScript (tāpat kā lielākajai daļai augsta līmeņa valodu) ir iebūvēta daudzu šo datu struktūru ieviešana.

Tomēr, zinot, kā ieviest šīs datu struktūras, jums būs milzīgas priekšrocības izstrādātāja darba meklējumos, un tas var būt noderīgi, mēģinot rakstīt augstas veiktspējas kodu.

Saistītie saraksti

Saistītais saraksts ir viena no pamata datu struktūrām. To bieži salīdzina ar masīvu, jo daudzas citas datu struktūras var ieviest ar masīvu vai saistītu sarakstu. Viņiem katram ir priekšrocības un trūkumi.

Saistītais saraksts sastāv no mezglu grupas, kas kopā apzīmē secību. Katrā mezglā ir divas lietas: faktiskie uzglabājamie dati (kas būtībā var būt jebkura veida dati) un rādītājs (vai saite) uz nākamo mezglu secībā. Ir arī divkārši saistīti saraksti, kur katram mezglam ir norāde gan uz nākamo vienumu, gan uz iepriekšējo saraksta vienumu.

Visvienkāršākās saistītā saraksta darbības ir vienuma pievienošana sarakstam, vienuma dzēšana no saraksta un saraksta meklēšana pēc elementa.

Šeit skatiet saistītā saraksta kodu JavaScript.

Saistītā saraksta laika sarežģītība

Algoritms Vidēji Sliktākajā gadījumā
Kosmoss 0 (n) 0 (n)
Meklēt 0 (n) 0 (n)
Ievietojiet 0 (1) 0 (1)
Dzēst 0 (1) 0 (1)

freeCodeCamp izaicinājumi

  • Darbs ar mezgliem saistītajā sarakstā
  • Izveidojiet saistīto sarakstu klasi
  • Noņemt elementus no saistītā saraksta
  • Meklēt saistītajā sarakstā
  • Noņemt elementus no saistītā saraksta pēc rādītāja
  • Pievienojiet saistītā saraksta elementus noteiktā rādītājā
  • Izveidojiet divkārši saistītu sarakstu
  • Apgrieziet divkārši saistīto sarakstu

Skursteņi

Steks ir pamata datu struktūra, kurā jūs varat ievietot vai dzēst vienumus tikai kaudzes augšdaļā. Tas ir kaut kā līdzīgs grāmatu kaudzei. Ja vēlaties aplūkot grāmatu kaudzes vidū, vispirms vispirms jānoņem visas grāmatas.

Steks tiek uzskatīts par LIFO (Last In First Out) - tas nozīmē, ka pēdējais vienums, ko ievietojat kaudzē, ir pirmais vienums, kas iznāk no kaudzes

Uz kaudzēm var veikt trīs galvenās darbības: vienuma ievietošana kaudzītē (saukta par “push”), vienuma dzēšana no kaudzes (saukta par “pop”) un kaudzes satura parādīšana (dažreiz saukta arī par “pip”) ').

Šeit skatiet skursteņa kodu JavaScript.

Steka laika sarežģītība

Algoritms Vidēji Sliktākajā gadījumā
Kosmoss 0 (n) 0 (n)
Meklēt 0 (n) 0 (n)
Ievietojiet 0 (1) 0 (1)
Dzēst 0 (1) 0 (1)

freeCodeCamp izaicinājumi

  • Uzziniet, kā darbojas kaudze
  • Izveidojiet kaudzes klasi

Rindas

Jūs varat domāt par rindu kā cilvēku rindu pie pārtikas preču veikala. Pirmais rindā ir pirmais, kas tiek pasniegts. Gluži kā rinda.

Rinda tiek uzskatīta par FIFO (First In First Out), lai parādītu veidu, kā tā piekļūst datiem. Tas nozīmē, ka pēc jauna elementa pievienošanas pirms jaunā elementa noņemšanas ir jānoņem visi iepriekš pievienotie elementi.

Rindai ir tikai divas galvenās darbības: enqueue un dequeue. Enqueue nozīmē objekta ievietošanu rindas aizmugurē un dequeue priekšējā priekšmeta noņemšanu.

Šeit skatiet rindas kodu JavaScript.

Rindas laika sarežģītība

Algoritms Vidēji Sliktākajā gadījumā
Kosmoss 0 (n) 0 (n)
Meklēt 0 (n) 0 (n)
Ievietojiet 0 (1) 0 (1)
Dzēst 0 (1) 0 (1)

freeCodeCamp izaicinājumi

  • Izveidojiet rindas klasi
  • Izveidojiet prioritātes rindas klasi
  • Izveidojiet apļveida rindu

Komplekti

Iestatītā datu struktūra saglabā vērtības bez īpašas secības un bez atkārtotām vērtībām. Papildus tam, ka kopai var pievienot un noņemt elementus, ir arī dažas citas svarīgas kopu funkcijas, kas darbojas vienlaikus ar divām kopām.

  • Savienība - tas apvieno visus vienumus no divām dažādām kopām un atgriež to kā jaunu kopu (bez dublikātiem).
  • Krustojums - ņemot vērā divas kopas, šī funkcija atgriež citu kopu, kurā ir visi vienumi, kas ir abu kopu daļa.
  • Atšķirība - tiek parādīts to vienumu saraksts, kuri ir vienā komplektā, bet NAV citā komplektā.
  • Apakškopa - atgriež Būla vērtību, kas parāda, vai visi vienas kopas elementi ir iekļauti citā kopā.

Šeit skatiet kodu, lai ieviestu JavaScript kopu.

freeCodeCamp izaicinājumi

  • Izveidojiet iestatītu klasi
  • Noņemt no komplekta
  • Komplekta izmērs
  • Izveidojiet savienojumu divos komplektos
  • Veiciet divu datu kopu krustojumu
  • Veiciet atšķirību starp diviem datu kopumiem
  • Veiciet divu datu kopu apakškopas pārbaudi
  • Izveidot un pievienot kopām ES6
  • Noņemiet vienumus no kopas ES6
  • ES6 komplektā izmantojiet .has un .size
  • ES5 Set () integrācijai izmantojiet Spread un Notes

Kartes

Karte ir datu struktūra, kurā dati tiek glabāti atslēgu / vērtību pāros, kur katrs taustiņš ir unikāls. Karti dažreiz sauc par asociatīvu masīvu vai vārdnīcu. To bieži izmanto ātrai datu meklēšanai. Maps ļauj veikt šādas darbības:

  • pāra pievienošana kolekcijai
  • pāra izņemšana no kolekcijas
  • esošā pāra modifikācija
  • vērtības meklēšana, kas saistīta ar konkrētu atslēgu

Šeit skatiet kodu, lai ieviestu karti JavaScript.

freeCodeCamp izaicinājumi

  • Izveidojiet kartes datu struktūru
  • Izveidojiet ES6 JavaScript karti

Hash tabulas

Hash tabula ir kartes datu struktūra, kas satur atslēgu / vērtību pārus. Tas izmanto jaucējfunkciju, lai aprēķinātu indeksu spaiņu vai slotu masīvā, no kuriem var atrast vēlamo vērtību.

Hash funkcija parasti ievada virkni kā ievadi, un tā izsniedz skaitlisku vērtību. Jaucējfunkcijai vienmēr vajadzētu dot vienu un to pašu izejas numuru vienai un tai pašai ieejai. Ja divām ieejām tiek jaukta viena un tā pati skaitliskā izeja, to sauc par sadursmi. Mērķis ir maz sadursmju.

Tātad, ievadot atslēgu / vērtību pāri jaukšanas tabulā, taustiņš tiek palaists cauri jaucējfunkcijai un pārvērsts par skaitli. Pēc tam šo skaitlisko vērtību izmanto kā faktisko atslēgu, ar kuru vērtība tiek saglabāta. Mēģinot vēlreiz piekļūt tam pašam taustiņam, jaukšanas funkcija atslēgu apstrādās un atgriezīs to pašu skaitlisko rezultātu. Pēc tam numurs tiks izmantots, lai meklētu saistīto vērtību. Tas nodrošina vidēji ļoti efektīvu O (1) uzmeklēšanas laiku.

Skatiet hash tabulas kodu šeit.

Hash galda sarežģītība

Algoritms Vidēji Sliktākajā gadījumā
Kosmoss 0 (n) 0 (n)
Meklēt 0 (1) 0 (n)
Ievietojiet 0 (1) 0 (n)
Dzēst 0 (1) 0 (n)

freeCodeCamp izaicinājumi

  • Izveidojiet Hash tabulu

Binārais meklēšanas koks

Koks ir datu struktūra, kas sastāv no mezgliem. Tam ir šādas īpašības:

  1. Katram kokam ir saknes mezgls (augšpusē).
  2. Saknes mezglā ir nulle vai vairāk bērnu mezglu.
  3. Katrā bērna mezglā ir nulle vai vairāk bērnu mezglu utt.

Binārā meklēšanas koks piebilst šīs divas īpašības:

  1. Katrā mezglā ir līdz diviem bērniem.
  2. Katram mezglam tā kreisie pēcteči ir mazāki nekā pašreizējais mezgls, kas ir mazāks par labajiem pēctečiem.

Binārie meklēšanas koki ļauj ātri meklēt, pievienot un noņemt vienumus. To iestatīšana nozīmē, ka vidēji katrs salīdzinājums ļauj operācijām izlaist apmēram pusi no koka, tādējādi katrai uzmeklēšanai, ievietošanai vai dzēšanai ir vajadzīgs laiks, proporcionāls kokā saglabāto vienumu skaita logaritmam.

Šeit skatiet binārā meklēšanas koka kodu JavaScript.

Binārā meklēšanas laika sarežģītība

Algoritms Vidēji Sliktākajā gadījumā
Kosmoss 0 (n) 0 (n)
Meklēt 0 (log n) 0 (n)
Ievietojiet 0 (log n) 0 (n)
Dzēst 0 (log n) 0 (n)

freeCodeCamp izaicinājumi

  • Binārā meklēšanas kokā atrodiet minimālo un maksimālo vērtību
  • Pievienojiet jaunu elementu binārā meklēšanas kokam
  • Pārbaudiet, vai elements atrodas binārā meklēšanas kokā
  • Atrodiet binārā meklēšanas koka minimālo un maksimālo augstumu
  • Binārā meklēšanas kokā izmantojiet dziļuma pirmo meklēšanu
  • Izmantojiet Breadth First Search binārā meklēšanas kokā
  • Lapas mezgla dzēšana binārā meklēšanas kokā
  • Dzēst mezglu ar vienu bērnu binārā meklēšanas kokā
  • Dzēst mezglu ar diviem bērniem binārā meklēšanas kokā
  • Apgrieziet bināro koku

Trie

Trie (izrunā 'try') jeb prefiksu koks ir sava veida meklēšanas koks. Trie saglabā datus pa soļiem, kur katrs solis ir mezgls trie. Mēģinājumi bieži tiek izmantoti vārdu glabāšanai, lai ātri meklētu, piemēram, vārdu automātiskās pabeigšanas funkcija.

Katrā valodas mezglā ir viens vārda burts. Jūs sekojat treja zariem, lai uzrakstītu vārdu pa vienam burtam. Darbības sāk sazaroties, kad burtu secība atšķiras no citiem vārdiem trie vai kad vārds beidzas. Katrā mezglā ir burts (dati) un būla skaitlis, kas norāda, vai mezgls ir pēdējais mezgls vārdā.

Paskaties uz attēlu, un jūs varat veidot vārdus. Vienmēr sāciet no saknes mezgla augšpusē un strādājiet uz leju. Šeit parādītajā trie satur vārdu bumba, sikspārnis, lelle, do, dork, dorm, send, sense.

Šeit skatiet trī kodu JavaScript.

freeCodeCamp izaicinājumi

  • Izveidojiet Trie meklēšanas koku

Binārais kaudze

Binārais kaudze ir vēl viens koka datu struktūras veids. Katrā mezglā ir ne vairāk kā divi bērni. Turklāt tas ir pilnīgs koks. Tas nozīmē, ka visi līmeņi ir pilnībā aizpildīti līdz pēdējam līmenim un pēdējais līmenis ir aizpildīts no kreisās uz labo.

Binārā kaudze var būt vai nu min kaudze, vai maksimālā kaudze. Maksimālā kaudzē vecāku mezglu atslēgas vienmēr ir lielākas vai vienādas ar bērnu atslēgām. Minūšu kaudzē vecāku mezglu atslēgas ir mazākas vai vienādas ar bērnu atslēgām.

Kārtība starp līmeņiem ir svarīga, bet mezglu secība tajā pašā līmenī nav svarīga. Attēlā jūs varat redzēt, ka min kaudzes trešajam līmenim ir vērtības 10, 6 un 12. Šie skaitļi nav sakārtoti.

Šeit skatiet kaudzes kodu JavaScript.

Binārā kaudzes laika sarežģītība

Algoritms Vidēji Sliktākajā gadījumā
Kosmoss 0 (n) 0 (n)
Meklēt 0 (1) 0 (log n)
Ievietojiet 0 (log n) 0 (log n)
Dzēst 0 (1) 0 (1)

freeCodeCamp izaicinājumi

  • Ievietojiet elementu Max Heap
  • Noņemiet elementu no maksimālās kaudzes
  • Ievietojiet kaudzes kārtošanu ar minimālu kaudzi

Grafiks

Grafiki ir mezglu (sauktu arī par virsotnēm) un savienojumu (sauktu par malām) kolekcijas starp tiem. Grafikus sauc arī par tīkliem.

Viens grafiku piemērs ir sociālais tīkls. Mezgli ir cilvēki, un malas ir draudzība.

Ir divi galvenie grafiku veidi: virzīti un nevirzīti. Nenovirzītie grafiki ir grafiki bez virziena malās starp mezgliem. Virzītie grafiki turpretī ir diagrammas, kuru malās ir virziens.

Divi izplatīti grafika attēlošanas veidi ir blakusesošo saraksts un blakusesības matrica.

Blakus esošo sarakstu var attēlot kā sarakstu, kur kreisajā pusē ir mezgls, un labajā pusē ir visi pārējie mezgli, ar kuriem tas ir savienots.

Blakus esošā matrica ir skaitļu režģis, kur katra rinda vai kolonna grafikā attēlo citu mezglu. Rindas un kolonnas krustojumā ir skaitlis, kas norāda attiecības. Nulles nozīmē, ka nav nekādu šķautņu vai attiecību. Vieni nozīmē, ka pastāv attiecības. Ciparus, kas lielāki par vienu, var izmantot, lai parādītu atšķirīgu svaru.

Traversal algoritmi ir algoritmi, lai pārvietotos vai apmeklētu mezglus diagrammā. Galvenie šķērsošanas algoritmu veidi ir meklēšana pēc platuma un dziļums. Viens no izmantošanas veidiem ir noteikt, cik tuvu mezgli atrodas saknes mezglam. Zemāk redzamajā videoklipā skatiet, kā ieviest plašāko meklēšanu JavaScript.

Skatiet kodu pirmās meklēšanas plašumam blakus esošās matricas diagrammā JavaScript.

Binārā meklēšanas laika sarežģītība

Algoritms Laiks
Uzglabāšana O (| V | + | E |)
Pievienojiet virsotni O (1)
Pievienot malu O (1)
Noņemiet Vertex O (| V | + | E |)
Noņemt Edge O (| E |)
Vaicājums O (| V |)

freeCodeCamp izaicinājumi

  • Blakusparādību saraksts
  • Adjacency Matrix
  • Saslimstības matrica
  • Pirmais platums
  • Dziļums - pirmā meklēšana

Vairāk

Grāmata Grokking Algorithms ir labākā grāmata par šo tēmu, ja esat jauns datu struktūru / algoritmu lietotājs un jums nav datorzinātņu. Lai izskaidrotu dažas šajā rakstā iekļautās datu struktūras, tiek izmantoti viegli saprotami paskaidrojumi un jautras, ar rokām zīmētas ilustrācijas (autors, kurš ir Etsy vadošais izstrādātājs).

Grokinga algoritmi: ilustrēts ceļvedis programmētājiem un citiem zinātkāriem cilvēkiem

Kopsavilkums Grokking Algoritmi ir pilnībā ilustrētas lietojamu rokasgrāmatu, kas māca jums, kā izmantot kopīgus algoritmus ... www.amazon.com

Vai arī varat apskatīt manu video kursu, kas balstīts uz šo grāmatu: Algoritmi kustībā no Manning Publications. Iegūstiet 39% atlaidi no mana kursa, izmantojot kodu ' 39carnes '!