A csatolt lista megvalósítása a JavaScript-ben

Programozás

Ha adatstruktúrákat tanul, a csatolt lista egy olyan adatstruktúra, amelyet ismernie kell. Ha nem igazán érted, vagy hogy miként valósul meg a JavaScript-ben, akkor ez a cikk itt segít.

Ebben a cikkben megvitatjuk, mi az a összekapcsolt lista, miben különbözik egy tömbtől, és hogyan lehet megvalósítani a JavaScript-ben. Kezdjük el.

Mi az a linkelt lista?

A kapcsolt lista egy tömbhöz hasonló lineáris adatszerkezet. A tömböktől eltérően azonban az elemek nem egy adott memóriahelyen vagy indexben vannak tárolva. Minden elem inkább különálló objektum, amely mutatót vagy hivatkozást tartalmaz a lista következő objektumára.

Minden elem (általában csomópontnak nevezzük) két elemet tartalmaz: a tárolt adatokat és a következő csomópontra mutató hivatkozást. Az adatok bármilyen érvényes adattípus lehetnek. Ezt az alábbi ábra szemlélteti.

Csatolt lista képe

A hivatkozott lista belépési pontját fejnek nevezzük. A fej hivatkozás a csatolt lista első csomópontjára. A lista utolsó csomópontja nullára mutat. Ha egy lista üres, a fej null hivatkozás.

A JavaScript-ben egy összekapcsolt lista így néz ki:

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

A linkelt listák előnye

  • A csomópontok könnyen eltávolíthatók vagy hozzáadhatók egy összekapcsolt listáról a teljes adatstruktúra átszervezése nélkül. Ez az egyik előnye a tömbökhöz képest.

A kapcsolt listák hátrányai

  • A linkelt listákban a keresési műveletek lassúak. A tömböktől eltérően az adatelemek véletlenszerű hozzáférése nem engedélyezett. A csomópontok egymás után érhetők el az első csomóponttól kezdve.
  • A mutatók tárolása miatt több memóriát használ, mint a tömbök.

Összekapcsolt listák típusai

Három típusú összekapcsolt lista létezik:

  • Egyszerűen összekapcsolt listák : Minden csomópont csak egy mutatót tartalmaz a következő csomópontra. Erről beszéltünk eddig.
  • Kétszer összekapcsolt listák : Minden csomópont tartalmaz két mutatót, egy mutatót a következő csomópontra és egy mutatót az előző csomópontra.
  • Körkörös összekapcsolt listák : A körkörös összekapcsolt listák a csatolt listák olyan változatai, amelyekben az utolsó csomópont az első csomópontra mutat, vagy bármely más előtte lévő csomópontra mutat, ezáltal hurkot alkotva.

Lista csomópont megvalósítása a JavaScript-ben

Mint korábban említettük, egy listacsomópont két elemet tartalmaz: az adatokat és a következő csomópontra mutató mutatót. A lista csomópontját a JavaScript-ben a következőképpen tudjuk megvalósítani:

class ListNode { constructor(data) { this.data = data this.next = null } }

Összekapcsolt lista megvalósítása a JavaScript-ben

Az alábbi kód egy összekapcsolt lista osztály megvalósítását mutatja egy konstruktorral. Figyelje meg, hogy ha a fejcsomópontot nem adják át, akkor a fej nullára inicializálódik.

class LinkedList { constructor(head = null) { this.head = head } }

Összedobva az egészet

Hozzunk létre egy összekapcsolt listát az imént létrehozott osztálytal. Először létrehozunk két lista csomópontok, node1valamint node2és egy mutatót csomópontból 1 2 csomópontra.

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

Ezután létrehozunk egy összekapcsolt listát a node1.

let list = new LinkedList(node1)

Próbáljuk meg elérni az imént létrehozott lista csomópontjait.

console.log(list.head.next.data) //returns 5

Néhány LinkedList módszer

Ezután négy segítő módszert vezetünk be a linkelt listához. Ők:

  1. méret()
  2. egyértelmű()
  3. getLast ()
  4. getFirst ()

1. méret ()

Ez a módszer a csatolt listában jelen lévő csomópontok számát adja vissza.

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; }

2. tiszta ()

Ez a módszer kiüríti a listát.

clear() { this.head = null; }

3. getLast ()

Ez a módszer a csatolt lista utolsó csomópontját adja vissza.

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst ()

Ez a módszer a csatolt lista első csomópontját adja vissza.

getFirst() { return this.head; }

Összegzés

Ebben a cikkben megvitattuk, mi is az a linkelt lista, és hogyan lehet azt megvalósítani a JavaScript-ben. Megbeszéltük a linkelt listák különféle típusait, valamint azok általános előnyeit és hátrányait.

Remélem tetszett olvasni.

Értesítést szeretne kapni, amikor új cikket teszek közzé? Kattints ide.