Az adatstruktúrák kritikus részét képezik a szoftverfejlesztésnek, és az egyik leggyakoribb téma a fejlesztői állásinterjúk kérdésében.
A jó hír az, hogy alapvetően csak az adatok rendszerezésére és tárolására szolgáló speciális formátumok.
10 leggyakoribb adatstruktúrát tanítok meg neked - itt, ebben a rövid cikkben.
Beágyazott videókat készítettem ezekhez az adatstruktúrákhoz. Mindegyikhez kapcsoltam kód példákat is, amelyek bemutatják, hogyan lehet ezeket megvalósítani a JavaScript-ben.
És hogy némi gyakorlatot kapjak, a freeCodeCamp tanterv kihívásaihoz kapcsolódtam.
Ne feledje, hogy ezen adatstruktúrák egy része az idő összetettségét tartalmazza a Big O jelölésben. Ez nem mindegyiknél szerepel, mivel az idő összetettsége néha a megvalósítás módján alapszik. Ha többet szeretne megtudni a Big O Notation-ról, nézze meg a róla szóló cikkemet vagy ezt a videót Briana Marie-tól.
Vegye figyelembe azt is, hogy annak ellenére, hogy bemutatom, hogyan lehet ezeket az adatstruktúrákat megvalósítani a JavaScript-ben, a legtöbbjükhöz soha nem kellene magának implementálnia őket, hacsak nem olyan alacsony szintű nyelvet használt, mint a C.
A JavaScript (mint a legtöbb magas szintű nyelv) ezeknek az adatstruktúráknak sok beépített megvalósítását tartalmazza.
Ennek ellenére az adatstruktúrák megvalósításának ismerete hatalmas előnyt jelent a fejlesztői álláskeresésben, és hasznos lehet, ha nagy teljesítményű kódot próbál írni.
Összekapcsolt listák
A linkelt lista az egyik legalapvetőbb adatstruktúra. Gyakran hasonlítják egy tömbhöz, mivel sok más adatstruktúra megvalósítható egy tömb vagy egy csatolt lista segítségével. Mindegyiküknek vannak előnyei és hátrányai.
A csatolt lista csomópontok csoportjából áll, amelyek együttesen egy szekvenciát képviselnek. Minden csomópont két dolgot tartalmaz: a tényleges tárolt adatokat (amelyek alapvetően bármilyen típusú adatok lehetnek), és egy mutatót (vagy linket) a sorozat következő csomópontjára. Vannak duplán összekapcsolt listák is, ahol minden csomópontnak van mutatója a lista következő elemére és az előző elemre is.
A csatolt listában a legalapvetőbb műveletek egy elem hozzáadása a listához, egy elem törlése a listáról, és a listán egy elem keresése.
Itt tekintheti meg a csatolt lista kódját a JavaScript-ben.
Összekapcsolt listaidő bonyolultsága
| Algoritmus | Átlagos | Legrosszabb esetben |
|---|---|---|
| Hely | 0 (n) | 0 (n) |
| Keresés | 0 (n) | 0 (n) |
| Helyezze be | 0 (1) | 0 (1) |
| Töröl | 0 (1) | 0 (1) |
freeCodeCamp kihívások
- Munka a csomópontokkal egy összekapcsolt listában
- Hozzon létre egy összekapcsolt lista osztályt
- Elemek eltávolítása a kapcsolt listáról
- Keresés egy összekapcsolt listában
- Távolítsa el az elemeket az összekapcsolt listáról index szerint
- Adjon elemeket egy meghatározott indexhez egy összekapcsolt listában
- Hozzon létre egy duplán összekapcsolt listát
- Fordítson meg egy duplán összekapcsolt listát
Verem
A verem egy olyan alapvető adatszerkezet, amelybe csak elemeket lehet beszúrni vagy törölni a verem tetején. Valahogy hasonló egy halom könyvhez. Ha meg akar nézni egy könyvet a verem közepén, akkor először le kell vennie az összes felette levő könyvet.
A verem LIFO-nak (Last In First Out) számít - vagyis a verembe utoljára feltett elem az első elem, amely a veremből kerül ki
Három fő művelet hajtható végre a veremeken: egy elem beszúrása a verembe (ún. „Push”), egy elem törlése a veremből (az úgynevezett „pop”), és a verem tartalmának megjelenítése (néha „pip” néven is) ').
Itt tekintheti meg a verem kódját a JavaScript-ben.
Veremidő bonyolultsága
| Algoritmus | Átlagos | Legrosszabb esetben |
|---|---|---|
| Hely | 0 (n) | 0 (n) |
| Keresés | 0 (n) | 0 (n) |
| Helyezze be | 0 (1) | 0 (1) |
| Töröl | 0 (1) | 0 (1) |
freeCodeCamp kihívások
- Ismerje meg, hogyan működik a verem
- Hozzon létre veremosztályt
Sorok
Gondolhat egy sorra, mint egy embersorra egy élelmiszerboltban. Az első a sorban az első, amelyet kiszolgálnak. Csakúgy, mint egy sor.
A sor FIFO-nak (First In First Out) tekinthető, hogy bemutassa az adatokhoz való hozzáférés módját. Ez azt jelenti, hogy egy új elem hozzáadása után minden új elemet el kell távolítani, mielőtt az új elem eltávolítható lenne.
A sornak csak két fő művelete van: enqueue és dequeue. Az enquue azt jelenti, hogy egy elemet be kell illeszteni a sor hátuljába, a dequeue pedig az elülső elem eltávolítását jelenti.
Itt tekintheti meg a várakozási sor kódját a JavaScript-ben.
A várakozási idő összetettsége
| Algoritmus | Átlagos | Legrosszabb esetben |
|---|---|---|
| Hely | 0 (n) | 0 (n) |
| Keresés | 0 (n) | 0 (n) |
| Helyezze be | 0 (1) | 0 (1) |
| Töröl | 0 (1) | 0 (1) |
freeCodeCamp kihívások
- Hozzon létre egy várólistát
- Hozzon létre egy prioritási sor osztályt
- Hozzon létre egy körsort
Készletek
A beállított adatszerkezet értékeket tárol különösebb sorrend nélkül és megismételt érték nélkül. Amellett, hogy elemeket lehet hozzáadni és eltávolítani egy halmazhoz, van még néhány fontos halmazfüggvény, amelyek egyszerre két halmazzal működnek.
- Unió - Ez két különböző halmaz összes elemét egyesíti, és ezt új halmazként adja vissza (duplikátumok nélkül).
- Metszéspont - Adva két halmazt, ez a függvény egy másik halmazt ad vissza, amelyben minden elem szerepel, amelyek mindkét halmaz részét képezik.
- Különbség - Ez egy olyan elemeket ad vissza, amelyek egy készletben vannak, de NEM egy másik készletben.
- Részhalmaz - Ez egy logikai értéket ad vissza, amely megmutatja, hogy egy halmaz összes eleme szerepel-e egy másik halmazban.
Itt tekintheti meg a kódot egy készlet használatához a JavaScript-ben.
freeCodeCamp kihívások
- Hozzon létre egy meghatározott osztályt
- Eltávolítás egy készletből
- A készlet mérete
- Végezz uniót két halmazon
- Végezzen metszést két adatsoron
- Végezzen különbséget két adatsoron
- Hajtson végre egy részhalmaz-ellenőrzést két adatsoron
- Hozzon létre és adjon hozzá halmazokhoz az ES6-ban
- Távolítson el elemeket egy készletből az ES6-ban
- Használja a .has és a .size méreteket egy ES6 készleten
- A Spread és a Notes használata az ES5 Set () integrációhoz
Térképek
A térkép olyan adatszerkezet, amely kulcs / érték párokban tárolja az adatokat, ahol minden kulcs egyedi. A térképet néha asszociatív tömbnek vagy szótárnak nevezik. Gyakran használják az adatok gyors keresésére. A Térkép a következő dolgokat teszi lehetővé:
- egy pár hozzáadása a gyűjteményhez
- egy pár eltávolítása a gyűjteményből
- egy meglévő pár módosítása
- egy adott kulcshoz társított érték megkeresése
Itt tekintheti meg a kódot a térkép JavaScript-beillesztéséhez.
freeCodeCamp kihívások
- Hozzon létre egy térképadat-struktúrát
- Hozzon létre egy ES6 JavaScript-térképet
Hash Tables
A hash tábla olyan térképi adatszerkezet, amely kulcs / érték párokat tartalmaz. Hash függvényt használ az index kiszámításához egy tömb vödörbe vagy slotba, amelyből a kívánt érték megtalálható.
A hash függvény általában egy karakterláncot vesz be, és numerikus értéket ad ki. A hash függvénynek mindig ugyanazt a kimeneti számot kell megadnia ugyanazon bemenethez. Ha két bemenet kivonatolódik ugyanahhoz a numerikus kimenethez, akkor ezt ütközésnek nevezzük. A cél az, hogy kevés ütközés legyen.
Tehát amikor beír egy kulcs / érték párot egy hash táblába, a kulcs fut a hash függvényen, és számgá alakul. Ezt a számértéket azután tényleges kulcsként használják, amelyet az érték tárol. Amikor újra megpróbálja elérni ugyanazt a gombot, a kivonatolási funkció feldolgozza a kulcsot, és ugyanazt a numerikus eredményt adja vissza. A számot ezután a társított érték megkeresésére használják. Ez átlagosan nagyon hatékony O (1) keresési időt biztosít.
Itt tekintheti meg a hash tábla kódját.
Hash táblázat bonyolultsága
| Algoritmus | Átlagos | Legrosszabb esetben |
|---|---|---|
| Hely | 0 (n) | 0 (n) |
| Keresés | 0 (1) | 0 (n) |
| Helyezze be | 0 (1) | 0 (n) |
| Töröl | 0 (1) | 0 (n) |
freeCodeCamp kihívások
- Hozzon létre egy hasítási táblázatot
Bináris keresési fa
A fa egy csomópontokból álló adatszerkezet. A következő jellemzőkkel rendelkezik:
- Minden fának van egy gyökércsomópontja (a tetején).
- A gyökércsomópontnak nulla vagy több gyermekcsomópontja van.
- Minden gyermekcsomópontnak nulla vagy több gyermekcsomópontja van, és így tovább.
A bináris keresési fa ezt a két jellemzőt adja hozzá:
- Minden csomópontnak legfeljebb két gyermeke van.
- Minden csomópontnál a bal leszármazottai kisebbek, mint a jelenlegi csomópontok, ami kevesebb, mint a jobb oldali leszármazottaké.
A bináris keresési fák lehetővé teszik az elemek gyors megkeresését, hozzáadását és eltávolítását. Beállításuk módja azt jelenti, hogy átlagosan minden egyes összehasonlítás lehetővé teszi a műveletek számára a fa körülbelül felének átugrását, így minden egyes megkeresés, beillesztés vagy törlés időt vesz igénybe a fában tárolt elemek számának logaritmusával arányosan.
Itt tekintheti meg a bináris keresőfa kódját a JavaScript-ben.
Bináris keresési idő összetettsége
| Algoritmus | Átlagos | Legrosszabb esetben |
|---|---|---|
| Hely | 0 (n) | 0 (n) |
| Keresés | 0 (log n) | 0 (n) |
| Helyezze be | 0 (log n) | 0 (n) |
| Töröl | 0 (log n) | 0 (n) |
freeCodeCamp kihívások
- Keresse meg a minimum és a maximális értéket egy bináris keresési fában
- Új elem hozzáadása a bináris keresési fához
- Ellenőrizze, hogy van-e elem egy bináris keresési fában
- Keresse meg a bináris keresési fa minimális és maximális magasságát
- Használja a Mélység első keresést bináris keresési fában
- Használja a Szélesség első keresését bináris keresési fában
- Levélcsomópont törlése a bináris keresési fából
- Töröljön egy csomópontot egy gyermekkel a bináris keresési fában
- Kétgyermekes csomópont törlése a bináris keresési fából
- Fordítson bináris fát
Trie
A trie (ejtsd: 'try'), vagy az előtagfa egyfajta keresőfa. Egy trie adatokat tárol olyan lépésekben, ahol minden lépés egy csomópont a trie-ben. A próbákat gyakran használják a szavak gyors keresés céljából történő tárolására, például egy szó automatikus kitöltési szolgáltatására.
A nyelvi trie minden csomópontja egy szó egy betűjét tartalmazza. A trie ágait követve betűket írhat egyszerre. A lépések akkor kezdenek elágazni, amikor a betűk sorrendje eltér a trie többi szavától, vagy amikor egy szó véget ér. Minden csomópont tartalmaz egy betűt (adatot) és egy logikai értéket, amely jelzi, hogy a csomópont a szó utolsó csomópontja.
Nézd meg a képet, és szavakat alkothatsz. Mindig a gyökércsomópontnál kezdje a tetején, és dolgozzon le. Az itt látható trie tartalmazza a labda, denevér, baba, do, dork, dorm, send, sense szót.
Itt tekintheti meg a trie kódját a JavaScript-ben.
freeCodeCamp kihívások
- Hozzon létre egy Trie keresőfát
Bináris kupac
A bináris halom egy másik típusú fa adatszerkezet. Minden csomópontnak legfeljebb két gyermeke van. Ez is egy teljes fa. Ez azt jelenti, hogy minden szint teljesen kitöltődik az utolsó szintig, az utolsó szint pedig balról jobbra.
A bináris halom lehet min halom vagy max halom. Max. Kupacban a szülőcsomópontok kulcsa mindig nagyobb vagy egyenlő, mint a gyerekeké. Min. Kupacban a szülőcsomópontok kulcsa kisebb vagy egyenlő, mint a gyerekeké.
A szintek közötti sorrend fontos, de az azonos szintű csomópontok sorrendje nem fontos. A képen láthatja, hogy a min halom harmadik szintjének értéke 10, 6 és 12. Ezek a számok nincsenek rendben.
Itt tekintheti meg a halom kódját a JavaScript-ben.
Bináris halom idő bonyolultsága
| Algoritmus | Átlagos | Legrosszabb esetben |
|---|---|---|
| Hely | 0 (n) | 0 (n) |
| Keresés | 0 (1) | 0 (log n) |
| Helyezze be | 0 (log n) | 0 (log n) |
| Töröl | 0 (1) | 0 (1) |
freeCodeCamp kihívások
- Helyezzen egy elemet egy kupacba
- Távolítson el egy elemet a maximális kupacból
- Halom rendezés megvalósítása egy min halommal
Grafikon
A grafikonok a csomópontok (más néven csúcsok) és a köztük lévő kapcsolatok (ún. Élek) gyűjteményei. A grafikonokat hálózatoknak is nevezik.
A grafikonok egyik példája a közösségi hálózat. A csomópontok emberek, az élek pedig barátság.
A grafikonoknak két fő típusa van: irányított és irányítatlan. Az irányítatlan grafikonok olyan gráfok, amelyeken nincs irány a csomópontok közötti éleken. Az irányított grafikonok ezzel szemben olyan grafikonok, amelyeknek az élén egy irány van.
A grafikon ábrázolásának két általános módja a szomszédsági lista és a szomszédsági mátrix.
A szomszédsági lista listaként ábrázolható, ahol a bal oldal a csomópont, a jobb oldalon pedig az összes többi csomópont, amelyhez csatlakozik.
A szomszédsági mátrix egy számrács, ahol minden sor vagy oszlop egy másik csomópontot képvisel a grafikonon. A sor és az oszlop metszéspontjában a kapcsolatot jelző szám található. A nullák azt jelentik, hogy nincs él vagy kapcsolat. Azok azt jelentik, hogy van kapcsolat. Az egynél nagyobb számok felhasználhatók különböző súlyok megjelenítésére.
A bejárási algoritmusok a gráf csomópontjainak bejárására vagy meglátogatására szolgáló algoritmusok. A bejárási algoritmusok fő típusai: szélesség-első keresés és mélység-első keresés. Az egyik felhasználás annak meghatározása, hogy a csomópontok milyen közel vannak a gyökércsomóponthoz. Az alábbi videóból megtudhatja, hogyan lehet a szélesebb körű keresést megvalósítani a JavaScript-ben.
Lásd a szélesség első keresésének kódját egy szomszédsági mátrixdiagramon JavaScript-ben.
Bináris keresési idő összetettsége
| Algoritmus | Idő |
|---|---|
| Tárolás | O (| V | + | E |) |
| Adja hozzá a Vertexet | O (1) |
| Add Edge | O (1) |
| Távolítsa el a Vertexet | O (| V | + | E |) |
| Távolítsa el az Edge elemet | O (| E |) |
| Lekérdezés | O (| V |) |
freeCodeCamp kihívások
- Adjacency List
- Adjacency Matrix
- Incidencia Mátrix
- Szélesség-első keresés
- Mélység-első keresés
Több
A Grokking Algorithms című könyv a legjobb könyv a témában, ha még nem ismeri az adatszerkezeteket / algoritmusokat, és nincs informatikai háttere. Könnyen érthető magyarázatokat és szórakoztató, kézzel rajzolt illusztrációkat használ (az Etsy vezető fejlesztője), hogy megmagyarázza a cikkben szereplő néhány adatstruktúrát.
Grokking algoritmusok: Illusztrált útmutató programozóknak és más kíváncsi embereknek
Összefoglalás A Grokking algoritmusok egy teljesen illusztrált, barátságos útmutató, amely megtanítja, hogyan kell alkalmazni a közös algoritmusokat a www.amazon.com webhelyen.
Vagy megnézheti a videó tanfolyamomat, amely a könyv alapján készült: Mozgásban lévő algoritmusok a Manning Publications-től. 39% kedvezményt kap a tanfolyamomból a ' 39carnes ' kód használatával !
