Kako implementirati povezani popis u JavaScript

Ako učite strukture podataka, povezani popis jedna je struktura podataka koju biste trebali znati. Ako ga stvarno ne razumijete ili kako je implementiran u JavaScript, ovaj će vam članak pomoći.

U ovom ćemo članku razgovarati o tome što je povezani popis, kako se razlikuje od niza i kako ga implementirati u JavaScript. Započnimo.

Što je povezani popis?

Povezani popis linearna je struktura podataka slična arrayu. Međutim, za razliku od nizova, elementi se ne pohranjuju na određeno mjesto memorije ili u indeks. Umjesto toga, svaki je element zasebni objekt koji sadrži pokazivač ili vezu do sljedećeg objekta na tom popisu.

Svaki element (obično nazvan čvorovi) sadrži dvije stavke: pohranjene podatke i vezu do sljedećeg čvora. Podaci mogu biti bilo koje valjane vrste podataka. To možete vidjeti na donjem dijagramu.

Slika povezanog popisa

Ulazna točka na povezani popis naziva se glava. Glava je referenca na prvi čvor na povezanom popisu. Posljednji čvor na popisu pokazuje nulu. Ako je popis prazan, glava je nula referenca.

U JavaScriptu povezani popis izgleda ovako:

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

Prednost povezanih popisa

  • Čvorovi se lako mogu ukloniti ili dodati s povezanog popisa bez reorganizacije cjelokupne strukture podataka. To je jedna prednost koju ima u odnosu na nizove.

Mane povezanih popisa

  • Operacije pretraživanja sporo su na povezanim popisima. Za razliku od nizova, nasumični pristup elementima podataka nije dopušten. Čvorovima se pristupa sekvencijalno počevši od prvog čvora.
  • Zbog pohrane pokazivača koristi više memorije nego nizova.

Vrste povezanih popisa

Postoje tri vrste povezanih popisa:

  • Popisi s pojedinačnom vezom : Svaki čvor sadrži samo jedan pokazivač na sljedeći čvor. O tome smo do sada razgovarali.
  • Dvostruko povezani popisi : Svaki čvor sadrži dva pokazivača, pokazivač na sljedeći čvor i pokazivač na prethodni čvor.
  • Kružno povezani popisi : Kružno povezani popisi varijacija su povezanog popisa u kojem posljednji čvor pokazuje na prvi čvor ili bilo koji drugi čvor prije njega, čineći tako petlju.

Implementacija čvora popisa u JavaScript

Kao što je ranije rečeno, čvor popisa sadrži dvije stavke: podatke i pokazivač na sljedeći čvor. Čvor popisa možemo implementirati u JavaScript na sljedeći način:

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

Implementacija povezanog popisa u JavaScript

Donji kod prikazuje implementaciju povezane klase popisa s konstruktorom. Primijetite da ako čvor glave nije proslijeđen, glava se inicijalizira na nulu.

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

Sve zajedno

Stvorimo povezani popis s razredom koji smo upravo kreirali. Prvo, mi stvaramo dva lista čvorova, node1a node2i pokazivač od čvora 1 do čvora 2.

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

Dalje ćemo stvoriti povezani popis s node1.

let list = new LinkedList(node1)

Pokušajmo pristupiti čvorovima na popisu koji smo upravo stvorili.

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

Neke metode LinkedList

Dalje ćemo implementirati četiri pomoćne metode za povezani popis. Oni su:

  1. veličina()
  2. čisto()
  3. getLast ()
  4. getFirst ()

1. veličina ()

Ova metoda vraća broj čvorova prisutnih na povezanom popisu.

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

2. jasno ()

Ova metoda isprazni popis.

clear() { this.head = null; }

3. getLast ()

Ova metoda vraća zadnji čvor povezanog popisa.

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

4. getFirst ()

Ova metoda vraća prvi čvor povezanog popisa.

getFirst() { return this.head; }

Sažetak

U ovom smo članku razgovarali o tome što je povezani popis i kako ga je moguće implementirati u JavaScript. Također smo razgovarali o različitim vrstama povezanih popisa kao i o njihovim ukupnim prednostima i nedostacima.

Nadam se da ste uživali čitajući ga.

Želite li dobiti obavijest kad objavim novi članak? Kliknite ovdje.