Implementiranje povezane liste u JavaScript-u

Ako učite strukture podataka, povezana lista je jedna struktura podataka koju biste trebali znati. Ako je zaista ne razumete ili ne razumete kako se implementira u JavaScript, ovaj članak je ovde da vam pomogne. U ovom članku ćemo govoriti o tome šta je povezana lista, kako se razlikuje od niza i kako implementirati u JavaScript. Hajde da počnemo.

Šta je povezana lista?

Povezana lista je linearna struktura podataka slična nizu. Međutim, za razliku od niza, elementi se ne pohranjuju na određenoj memorijskoj lokaciji ili indeksu. Pre će biti da je svaki element zaseban objekat koji sadrži pokazivač ili vezu do sledećeg objekta na toj listi.

Svaki element (koji se obično naziva čvor) sadrži dve stavke: pohranjeni podaci i veza do sljedećeg čvora. Podaci mogu biti bilo koji važeći tip podataka. To možete videti na donjem dijagramu.

Tačka ulaska na povezanu listu naziva se glava. Glava je referenca na prvi čvor na povezanoj listi. Poslednji čvor na listi ukazuje na nulu. Ako je lista prazna, glava je nulta referenca.

U JavaScript-u povezana lista izgleda ovako:

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

Prednost povezanih lista:

Čvorovi se mogu lako ukloniti ili dodati sa povezane liste bez reorganizacije čitave strukture podataka. Ovo je jedna prednost koju ima nad nizovima.

Mane povezanih lista:

Operacije pretraživanja su spojene na povezanim listama. Za razliku od niza, slučajni pristup elementima podataka nije dozvoljen. Čvorovima se pristupa sekvencijalno počevši od prvog čvora.
Koristi više memorije nego nizova zbog skladištenja pokazivača.

Tipovi povezanih lista:

Postoje tri vrste povezanih lista

Popis pojedinačno povezanih: Svaki čvor sadrži samo jedan pokazivač na sledeći čvor. O ovome smo do sada razgovarali.

Dvostruko povezane liste: Svaki čvor sadrži dva pokazivača, pokazivač na sledeći čvor i pokazivač na prethodni čvor.

Kružne povezane liste: Kružna povezana lista je varijacija povezane liste u kojoj poslednji čvor upućuje na prvi čvor ili bilo koji drugi čvor pre nego što formira petlju.

Implementiranje Node liste u JavaScript

Kao što je ranije rečeno, čvor liste sadrži dve stavke: podatke i pokazivač na sledeći čvor. Možemo implementirati Node liste u JavaScript na sledeći način:

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

Implementiranje povezane liste u JavaScript

Donji kod prikazuje implementaciju povezane klase lista s konstruktorom. Primetite da ako glavni čvor nije prošao, glava se inicijalizira na nulu.

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

Sastavljanje svega

Kreirajmo povezanu listu sa klasom koju smo upravo kreirali. Prvo stvaramo dva čvora liste, node1 i node2 i pokazivač od čvora 1 do čvora 2.

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

Sledeće je pravljenje povezane liste sa node1

let list = new LinkedList(node1)

Pokušajmo da pristupimo čvorovima na listi koju smo upravo napravili

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

Neke od LinkedList metoda

Sledeće ćemo implementirati četiri pomoćne metode za povezanu listu. One su:

  1. size()
  2. clear()
  3. getLast()
  4. getFirst()

size()

Ovom metodom vraćate broj čvorova prisutnih na povezanoj listi.

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

clear()

Ova metoda ispraznjuje spisak.

clear() {
    this.head = null;
}

getLast()

Ova metoda vraća poslednji čvor povezane liste.

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

getFirst()

Ova metoda vraća prvi čvor povezane liste.

getFirst() {
    return this.head;
}

Zaključak

U ovom članku smo razgovarali o tome šta je povezana lista i kako se ona može implementirati u JavaScript. Takođe smo razgovarali o različitim vrstama povezanih lista i njenim prednostima i nedostacima.

REACT OSNOVE U 10 MINUTA!

Hvala na čitanju i Happy Hacking!

Izvor: Stitonosa.com

Leave a Reply

Your email address will not be published. Required fields are marked *

Translate to: