Hvordan implementere en koblet listedatastruktur i JavaScript?

JavaScript er et nettprogrammeringsspråk som brukes til å gjøre våre websider og webapplikasjoner dynamiske og interaktive ved å gi dem muligheten til å tenke og handle. Som alle andre programmeringsspråk tilbyr JavaScript oss matriser som er en samling av forskjellige elementer som er lagret i en enkelt variabel. Begrensningen av en matrise er at den lagres fortløpende ved et bestemt minne i vårt system, og for å løse dette problemet bruker vi en koblet liste.

Koblet liste

De koblede listene er som matriser bortsett fra at elementene i en koblet liste ikke lagres på et spesifikt minneplass eller indeks, og hvert element er et eget uavhengig objekt som er koblet til neste element ved å ha en peker eller lenke til det elementet.

Hver koblet liste inneholder et hode (første node), lengde (størrelse på den koblede listen) og en hale (siste node) egenskap, og hvert element i en koblet liste kalles en node og hver node har en verdi som er lagret i den og lenken til neste node. Hvis den gjeldende noden er halen, vil lenken være null som ikke peker på noen annen node. Den koblede listen inneholder ikke indekser i motsetning til matriser som har indekser e.g 0,1,2 ... og så videre.

Koblede lister i JavaScript kan demonstreres som følger:

// koblet liste
const linkedList =
// Hver node har en verdi og peker
// første peker er overskriften
hode:
Verdi: 6
Neste:
Verdi: 10
Neste:
Verdi: 12
Neste:
Verdi: 3
Neste: NULL





;

Koblet listefordel er at elementer (noder) enkelt blir lagt til og fjernet fra den koblede listen uten å justere hele koblede listen. Ulempen med en koblet liste er at den trenger mer minne for lagring, da vi nå har en ekstra peker som vi lagrer sammen med verdien av elementet.

Koblede lister er av tre typer som er beskrevet nedenfor:

• Den enkeltkoblede listen har bare en peker som peker på noden ved siden av.
• Den dobbeltkoblede er basert på to-poeng der den første peker på noden som ligger bak den, og den andre peker på noden ved siden av.
• Den sirkulære koblede listen hvis halen inneholder en peker til hodet og dermed danner en syklus.

Koblet listeimplementering

La oss først lage en node som har to egenskaper en verdi og en peker som vi vil lage en klasse med navnet på ListNode som har disse to egenskapene:

Klasselister
konstruktør (verdi)
dette.verdi = verdi
dette.Neste = null

Nå som vi vet hvordan vi oppretter en node, la oss opprette en koblet liste der standardverdien på hodet vil være null:

klasse LinkedList
konstruktør (head = null)
dette.hode = hode

La oss nå initialisere den koblede listen med to noder og legge til en peker fra hodet eller noden 1 til den andre noden:

var node1 = ny listNode (3);
var node2 = ny listNode (4);
Node1.neste = node2;

Neste trinn er å initialisere den koblede listen med Node1 på følgende måte:

var liste = ny LinkedList (Node1);

Hele koden er gitt nedenfor med konsolllogging av Node2 -verdien:

// Opprette node
Klasselister
konstruktør (verdi)
// konstruktørinitialiserende verdi og neste peker
dette.verdi = verdi
dette.Neste = null


klasse LinkedList
// Linked List Constructor
konstruktør (head = null)
dette.hode = hode


// Initialisering av opprettede noder
var node1 = ny listNode (3);
var node2 = ny listNode (4);
Node1.neste = node2;
// Initialisere koblet liste
var liste = ny LinkedList (Node1);
// viser utdata fra den andre noden
konsoll.Logg (liste.hode.NESTE.verdi) // 4

Koblede listemetoder

Nå som vi er ferdige med å implementere den koblede listen, la oss spille eller manipulere den koblede listen ved å implementere flere metoder for å benytte oss av de koblede listene (Helper Methods):

Den første hjelperemetoden vi vil definere er størrelse() Metode i klassen LinkedList som vil returnere lengden på den koblede listen:

størrelse = () =>
La Count = 0;
La Node = dette.hode;
// loop for å iterere over koblet liste
mens (node)
telle ++;
Node = node.NESTE

returantall;

I denne koden først erklærer vi en dummy -variabel telle lagrer 0 i den og lagrer deretter pekeren på hodet i Node variabel. Så erklærte vi en sløyfe som vil iterere over den koblede listen og øke telle variabel.

Neste hjelperemetode vil være getFirst () Metode der hodepekeren vil bli returnert:

getFirst = () =>
Returner dette.hode.verdi;

Vi kan også få den siste noden på den koblede listen på følgende måte:

getLast = () =>
La lastNode = dette.hode;
if (lastNode)
mens (lastNode.neste)
lastNode = lastNode.NESTE


Returner LastNode.verdi

Hele koden er nå gitt nedenfor med å vise utgangen fra den andre nodeverdien, størrelsen på koblet liste, første nodeverdi og den siste nodeverdien i samme rekkefølge:

// Opprette node
Klasselister
konstruktør (verdi)
dette.verdi = verdi
dette.Neste = null


// Opprette koblet liste
klasse LinkedList
konstruktør (head = null)
dette.hode = hode

størrelse = () =>
La Count = 0;
La Node = dette.hode;
// loop for å iterere over koblet liste
mens (node)
telle ++;
Node = node.NESTE

returantall;

getFirst = () =>
Returner dette.hode.verdi;

getLast = () =>
La lastNode = dette.hode;
if (lastNode)
mens (lastNode.neste)
lastNode = lastNode.NESTE


Returner LastNode.verdi


// Initialisering av opprettede noder
var node1 = ny listNode (3);
var node2 = ny listNode (4);
Node1.neste = node2;
// Initialisere koblet liste
var liste = ny LinkedList (Node1);
// viser utdata fra den andre noden
konsoll.Logg ("Second Node Value:", liste.hode.NESTE.verdi) // 4
// viser størrelsen på den koblede listen
konsoll.Logg ("Størrelse på koblet liste:", liste.størrelse());
// viser første nodeverdi
konsoll.Logg ("Første nodeverdi:", liste.getFirst ());
// viser siste nodeverdi
konsoll.Logg ("Siste nodeverdi:", liste.getLast ());

Konklusjon

Etter matriser er en koblet liste den nest mest brukte datastrukturen på ethvert programmeringsspråk. En koblet liste er som en matrise som lagrer en samling av forskjellige elementer med forskjellen at hvert element (node) på en koblet liste er et objekt som inneholder en verdi av elementet og en peker som peker på neste node, og dermed kobler hvert element og Den andre forskjellen er at elementene ikke lagres på et bestemt minneplass i en lenket liste.

I dette innlegget så vi hva koblede lister er, fordelene og ulempene med koblede lister, hvilke typer koblede lister og hvordan du implementerer koblet listedatastruktur i JavaScript.