Kaip įdiegti susietą sąrašą „JavaScript“

Jei mokotės duomenų struktūrų, susietas sąrašas yra viena duomenų struktūra, kurią turėtumėte žinoti. Jei iš tikrųjų to nesuprantate arba kaip tai įdiegta „JavaScript“, šis straipsnis yra jums padėti.

Šiame straipsnyje aptarsime, kas yra susietas sąrašas, kuo jis skiriasi nuo masyvo ir kaip jį įdiegti „JavaScript“. Pradėkime.

Kas yra susietasis sąrašas?

Susietas sąrašas yra linijinė duomenų struktūra, panaši į masyvą. Tačiau, skirtingai nuo masyvų, elementai nėra saugomi tam tikroje atminties vietoje ar rodyklėje. Kiekvienas elementas yra atskiras objektas, kuriame yra žymeklis arba nuoroda į kitą to sąrašo objektą.

Kiekviename elemente (paprastai vadinamame mazgu) yra du elementai: saugomi duomenys ir nuoroda į kitą mazgą. Duomenys gali būti bet kokie galiojantys duomenų tipai. Tai galite pamatyti iliustruotoje diagramoje.

Susieto sąrašo vaizdas

Susieto sąrašo įvesties taškas vadinamas galva. Galva yra nuoroda į pirmąjį susietojo sąrašo mazgą. Paskutinis sąrašo mazgas nurodo nulį. Jei sąrašas tuščias, antraštė yra nulinė nuoroda.

„JavaScript“ susietas sąrašas atrodo taip:

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

Susietų sąrašų pranašumas

  • Mazgus galima lengvai pašalinti arba pridėti iš susieto sąrašo, nepertvarkant visos duomenų struktūros. Tai yra vienas privalumas, palyginti su masyvais.

Susietų sąrašų trūkumai

  • Susietuose sąrašuose paieškos operacijos vyksta lėtai. Skirtingai nuo masyvų, atsitiktinė prieiga prie duomenų elementų neleidžiama. Prie mazgų galima prisijungti nuosekliai pradedant nuo pirmo mazgo.
  • Dėl rodyklių saugojimo jis naudoja daugiau atminties nei masyvai.

Susietų sąrašų tipai

Yra trys susietų sąrašų tipai:

  • Atskirai susieti sąrašai : Kiekviename mazge yra tik vienas rodiklis į kitą mazgą. Apie tai kalbėjome iki šiol.
  • Dvigubai susieti sąrašai : Kiekviename mazge yra du rodyklės, rodyklė į kitą mazgą ir ankstesnio mazgo rodyklė.
  • Apskrito susieti sąrašai : Apskrito susieti sąrašai yra susieto sąrašo variantas, kuriame paskutinis mazgas nukreipia į pirmąjį mazgą ar bet kurį kitą prieš jį esantį mazgą ir taip suformuoja kilpą.

Sąrašo mazgo diegimas „JavaScript“

Kaip minėta anksčiau, sąrašo mazge yra du elementai: duomenys ir rodyklė į kitą mazgą. Sąrašo mazgą „JavaScript“ galime įdiegti taip:

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

Susieto sąrašo diegimas „JavaScript“

Žemiau pateiktas kodas rodo susieto sąrašo klasės įgyvendinimą su konstruktoriumi. Atkreipkite dėmesį, kad jei galvos mazgas neperduodamas, galva inicializuojama į nulį.

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

Viską sujungus

Sukurkime susietą sąrašą su ką tik sukurta klase. Pirma, mes sukurti du sąrašas mazgus, node1ir node2ir rodyklė nuo mazgo 1 mazgas 2.

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

Tada sukursime susietą sąrašą su node1.

let list = new LinkedList(node1)

Pabandykime prieiti prie ką tik sukurto sąrašo mazgų.

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

Kai kurie „LinkedList“ metodai

Toliau įgyvendinsime keturis susietojo sąrašo pagalbininkų metodus. Jie yra:

  1. dydis ()
  2. aišku ()
  3. „getLast“ ()
  4. „getFirst“ ()

1. dydis ()

Šis metodas pateikia susietame sąraše esančių mazgų skaičių.

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

2. aišku ()

Šis metodas ištuština sąrašą.

clear() { this.head = null; }

3. „getLast“ ()

Šis metodas pateikia paskutinį susieto sąrašo mazgą.

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

4. „getFirst“ ()

Šis metodas pateikia pirmąjį susieto sąrašo mazgą.

getFirst() { return this.head; }

Santrauka

Šiame straipsnyje aptarėme, kas yra susietas sąrašas ir kaip jį galima įdiegti „JavaScript“. Mes taip pat aptarėme įvairius susietų sąrašų tipus, taip pat jų bendruosius pranašumus ir trūkumus.

Tikiuosi, kad jums patiko ją skaityti.

Norite gauti pranešimą, kai paskelbsiu naują straipsnį? Paspauskite čia.