Kuidas lingitud loendit JavaScripti rakendada

Kui õpite andmestruktuure, on lingitud loend üks andmestruktuur, mida peaksite teadma. Kui te sellest tegelikult aru ei saa või kuidas seda JavaScripti rakendatakse, on see artikkel teile abiks.

Selles artiklis käsitleme, mis on lingitud loend, kuidas see erineb massiivist ja kuidas seda JavaScripti rakendada. Alustame.

Mis on lingitud loend?

Lingitud loend on massiiviga sarnane lineaarne andmestruktuur. Erinevalt massiividest ei salvestata elemente kindlasse mälukohta ega registrisse. Iga element on pigem eraldi objekt, mis sisaldab kursorit või linki loendis järgmise objekti juurde.

Iga element (tavaliselt nimetatakse sõlmedeks) sisaldab kahte üksust: salvestatud andmeid ja linki järgmisele sõlmele. Andmed võivad olla mis tahes kehtivad andmetüübid. Seda näete illustreerituna alloleval skeemil.

Lingitud loendi pilt

Lingitud loendi sisestuspunkti nimetatakse peaks. Pea on viide lingitud loendi esimesele sõlmele. Loendi viimane sõlm osutab nullile. Kui loend on tühi, on pea nullviide.

JavaScriptis näeb lingitud loend välja järgmine:

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

Lingitud loendite eelis

  • Sõlmi saab lingitud loendist hõlpsasti eemaldada või lisada kogu andmestruktuuri ümber korraldamata. See on üks eelis massiivide ees.

Lingitud loendite puudused

  • Lingitud loendites on otsingutoimingud aeglased. Erinevalt massiividest pole andmeelementide juhuslik juurdepääs lubatud. Noodidele pääseb järjestikku alates esimesest sõlmest.
  • Osutajate salvestamise tõttu kasutab see rohkem mälu kui massiivid.

Lingitud loendite tüübid

Lingitud loendeid on kolme tüüpi:

  • Üksikult lingitud loendid : iga sõlm sisaldab ainult ühte osutust järgmise sõlme juurde. Sellest oleme seni rääkinud.
  • Kahekordse lingiga loendid : iga sõlm sisaldab kahte osutit, kursorit järgmisele ja eelmisele sõlmele.
  • Ringikujulised lingitud loendid : ümmargused lingitud loendid on variatsioon lingitud loendist, milles viimane sõlm osutab esimesele sõlmele või mis tahes muule enne seda olevale sõlmele, moodustades seeläbi silmuse.

Loendisõlme juurutamine JavaScripti

Nagu varem öeldud, sisaldab loendisõlm kahte elementi: andmed ja järgmise sõlme osuti. Saame JavaScripti loendisõlme rakendada järgmiselt:

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

Lingitud loendi juurutamine JavaScripti

Allolev kood näitab lingitud loendiklassi rakendamist koos konstruktoriga. Pange tähele, et kui peasõlme ei edastata, lähtestatakse pea nulliks.

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

Kõike kokku panema

Koostame äsja loodud klassiga lingitud loendi. Esiteks, me luua kaks nimekirja tippu, node1ja node2ja osuti sõlmest 1 sõlmega 2.

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

Järgmisena loome lingitud loendi koos node1.

let list = new LinkedList(node1)

Proovime juurde pääseda äsja loodud loendi sõlmedele.

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

Mõned LinkedListi meetodid

Järgmisena rakendame lingitud loendi jaoks neli abimeetodit. Nemad on:

  1. suurus ()
  2. selge ()
  3. getLast ()
  4. getFirst ()

1. suurus ()

See meetod tagastab lingitud loendis olevate sõlmede arvu.

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

2. selge ()

See meetod tühistab loendi.

clear() { this.head = null; }

3. getLast ()

See meetod tagastab lingitud loendi viimase sõlme.

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

4. getFirst ()

See meetod tagastab lingitud loendi esimese sõlme.

getFirst() { return this.head; }

Kokkuvõte

Selles artiklis käsitlesime, mis on lingitud loend ja kuidas seda JavaScripti rakendada. Arutasime ka lingitud loendite eri tüüpe ning nende üldisi eeliseid ja puudusi.

Loodan, et teile meeldis seda lugeda.

Kas soovite uue artikli avaldamise korral märguandeid saada? Kliki siia.