Articles

Singly Linked List i JavaScript

for at få en klar forståelse af singly linked list, implementerer jeg LinkedList class i JavaScript.

hver node af linket liste vil have to attributter: værdi & næste, og linket liste vil have hoved, hale og længde attribut.

https://gist.github.com/GAierken/eb9583bc1ffa78b8e1bb7438a7a49014

Push

hvordan kan vi skubbe en ny node i slutningen af vores liste? Lad os lave en push-funktion. Først skal vi oprette en ny node ved hjælp af den givne værdi, kontrollere om listen har et hoved (er det tomt?) og glem ikke at øge størrelsen på listen.

https://gist.github.com/GAierken/4e44162c8fefe746680e67ea65bf9397

Pop

med pushing skal vi tænke på at poppe, slette det sidste element. Hvis der ikke er nogen node, skal du vende tilbage udefineret, ellers, løbe gennem listen, indtil vi når halen, indstil den næste egenskab for den næstsidste node til at være null, gør den næstsidste til at være halen, glem ikke at formindske størrelsen på listen.

https://gist.github.com/GAierken/2c24fecb26f7453879ab471190fcba1e

Skift

for at slette det første element, skift som normalt, kontroller, om listen er tom. Først skal du gemme det aktuelle hoved i en variabel, indstille hovedet til at være det aktuelle Hoveds næste, Formindsk længden.

https://gist.github.com/GAierken/e6a11cdaf63d9620db33cef58d0a9507

næste attribut for den indkommende node, øg størrelsen.

https://gist.github.com/GAierken/95cbf790f1b6e03711f2460eb7951aa4

Get

selvom linket liste ikke har indekser, kan vi stadig finde noden ved givet indeks. Sørg først for, at det givne indeks er større end nul og mindre eller lig med længden på listen. Så løber vi gennem listen, indtil vi når indekset.

https://gist.github.com/GAierken/6475bb388fe8b0f2b7f6507bb3cab446

Set

Hvad hvis vi vil ændre en node i vores liste? Vi finder noden med get () og indstiller noden med givne data.

https://gist.github.com/GAierken/e9b0bb11849219914e2b3ee7b215d5d2

Indsæt

Når vi vil indsætte en ny node i listen, skal du først kontrollere, om indekset er større end 0 og mindre end længden. Hvis indekset er længden, bruger vi bare push(), hvis indekset er 0, bruger vi unshift(). For andre indekser skal vi få noden ved indekset-1 og indstille den næste egenskab for den node til at være den nye node, og den næste egenskab for den nye node til at være den forrige næste egenskab, så øger vi længden.

https://gist.github.com/GAierken/08c88867ddb514de6ef4ddb3923a4117

Fjern

i modsætning til pop og unshift fjerner funktionen noden ved givet indeks. Som sædvanligt skal du kontrollere, om indekset er gyldigt, hvis indekset er lig med længden-1 eller 0, skal du bruge pop eller shift. Ellers får vi noden ved indekset-1, Indstil den næste egenskab på den node til at være den næste af den næste ejendom, efter at vi formindsker størrelsen.

https://gist.github.com/GAierken/e888104f65a836925b11e102584edd76

Reverse

det ultimative omvendte spørgsmål! Hvordan ændrer vi listen? Først bytter vi hoved og hale, erklærer næste og forrige, indstiller den forrige som null. Vi løber gennem listen.

https://gist.github.com/GAierken/556c13f4ccbc5bcd49584bd662b553de