Sådan implementeres en sammenkædet liste i JavaScript

Hvis du lærer datastrukturer, er en linket liste en datastruktur, du bør kende. Hvis du ikke rigtig forstår det, eller hvordan det implementeres i JavaScript, er denne artikel her for at hjælpe dig.

I denne artikel vil vi diskutere, hvad en linket liste er, hvordan den adskiller sig fra en matrix, og hvordan man implementerer den i JavaScript. Lad os komme igang.

Hvad er en sammenkædet liste?

En linket liste er en lineær datastruktur, der ligner en matrix. I modsætning til arrays gemmes elementer imidlertid ikke et bestemt hukommelsessted eller indeks. Hvert element er snarere et separat objekt, der indeholder en markør eller et link til det næste objekt på listen.

Hvert element (ofte kaldet noder) indeholder to elementer: de gemte data og et link til den næste node. Dataene kan være en hvilken som helst gyldig datatype. Du kan se dette illustreret i nedenstående diagram.

Billede af en linket liste

Indgangspunktet til en linket liste kaldes hovedet. Hovedet er en henvisning til den første node på den linkede liste. Den sidste node på listen peger på null. Hvis en liste er tom, er hovedet en null-reference.

I JavaScript ser en linket liste sådan ud:

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

En fordel ved sammenkædede lister

  • Noder kan let fjernes eller tilføjes fra en linket liste uden at omorganisere hele datastrukturen. Dette er en fordel i forhold til arrays.

Ulemper ved sammenkædede lister

  • Søgeoperationer er langsomme på sammenkædede lister. I modsætning til arrays er tilfældig adgang til dataelementer ikke tilladt. Noder tilgås sekventielt startende fra den første knude.
  • Det bruger mere hukommelse end arrays på grund af lagring af markørerne.

Typer af sammenkædede lister

Der er tre typer af sammenkædede lister:

  • Enkelt forbundne lister : Hver node indeholder kun en markør til den næste node. Dette er det, vi har talt om indtil videre.
  • Dobbelt sammenkædede lister : Hver node indeholder to markører, en markør til den næste node og en markør til den forrige node.
  • Cirkulære sammenkædede lister : Cirkulære sammenkædede lister er en variation af en sammenkædet liste, hvor den sidste node peger på den første node eller en hvilken som helst anden node før den og derved danner en loop.

Implementering af en listeknude i JavaScript

Som tidligere nævnt indeholder en listeknude to elementer: dataene og markøren til den næste knude. Vi kan implementere en listeknude i JavaScript som følger:

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

Implementering af en sammenkædet liste i JavaScript

Koden nedenfor viser implementeringen af ​​en linket listeklasse med en konstruktør. Bemærk, at hvis hovednoden ikke passeres, initialiseres hovedet til null.

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

Samler det hele

Lad os oprette en linket liste med den klasse, vi lige har oprettet. Først skaber vi to list noder, node1og node2og en pointer fra knudepunkt 1 til knudepunkt 2.

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

Derefter opretter vi en sammenkædet liste med node1.

let list = new LinkedList(node1)

Lad os prøve at få adgang til knudepunkterne på den liste, vi lige har oprettet.

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

Nogle LinkedList-metoder

Derefter implementerer vi fire hjælpemetoder til den linkede liste. De er:

  1. størrelse()
  2. klar()
  3. getLast ()
  4. getFirst ()

1. størrelse ()

Denne metode returnerer antallet af noder, der findes på den linkede liste.

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

2. ryd ()

Denne metode tømmer listen.

clear() { this.head = null; }

3. getLast ()

Denne metode returnerer den sidste node på den linkede liste.

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

4. getFirst ()

Denne metode returnerer den første node på den linkede liste.

getFirst() { return this.head; }

Resumé

I denne artikel diskuterede vi, hvad en linket liste er, og hvordan den kan implementeres i JavaScript. Vi diskuterede også de forskellige typer sammenkædede lister samt deres overordnede fordele og ulemper.

Jeg håber, du nød at læse det.

Vil du blive underrettet, når jeg offentliggør en ny artikel? Klik her.