Articles

Einfach verknüpfte Liste in JavaScript

Um ein klares Verständnis der einfach verknüpften Liste zu erhalten, implementiere ich die LinkedList-Klasse in JavaScript.

Jeder Knoten der verknüpften Liste hat zwei Attribute: value & next , und die verknüpfte Liste hat die Attribute head, tail und length .

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

Push

Wie können wir einen neuen Knoten an das Ende unserer Liste schieben? Machen wir eine Push-Funktion. Zuerst müssen wir einen neuen Knoten mit dem angegebenen Wert erstellen und prüfen, ob die Liste einen Kopf hat (ist sie leer?) und vergessen Sie nicht, die Größe der Liste zu erhöhen.

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

Pop

Beim Drücken müssen wir darüber nachdenken, das letzte Element zu löschen. Wenn es keinen Knoten gibt, return undefined, else, Schleife durch die Liste, bis wir den Schwanz erreichen, Setzen Sie die nächste Eigenschaft des vorletzten Knotens auf null, Machen Sie den vorletzten zum Schwanz, vergessen Sie nicht, die Größe der Liste zu verringern.

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

Shift

Überprüfen Sie zum Löschen des ersten Elements wie gewohnt, ob die Liste leer ist. Speichern Sie zuerst den aktuellen Kopf in einer Variablen, setzen Sie den Kopf auf den nächsten des aktuellen Kopfes und dekrementieren Sie die Länge.

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

Unshift

Um einen Knoten am Anfang der Liste einzufügen, überprüfen Sie, ob die Liste leer ist. Wenn nicht, setzen wir den aktuellen Kopf als nächstes Attribut des eingehenden Knotens , erhöhen Sie die Größe.

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

Get

Obwohl die verknüpfte Liste keine Indizes hat, können wir den Knoten immer noch anhand des angegebenen Index finden. Stellen Sie zunächst sicher, dass der angegebene Index größer als Null und kleiner oder gleich der Länge der Liste ist. Dann durchlaufen wir die Liste, bis wir den Index erreichen.

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

Set

Was ist, wenn wir einen Knoten in unserer Liste ändern möchten? Wir finden den Knoten mit get () und setzen den Knoten mit den angegebenen Daten.

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

Einfügen

Wenn wir einen neuen Knoten in die Liste einfügen möchten, überprüfen Sie zuerst, ob der Index größer als 0 und kleiner als die Länge ist. Wenn index die Länge ist, verwenden wir einfach push(), wenn der Index 0 ist, verwenden wir unshift(). Für andere Indizes müssen wir den Knoten auf den Index-1 setzen und die nächste Eigenschaft dieses Knotens auf den neuen Knoten und die nächste Eigenschaft des neuen Knotens auf die vorherige nächste Eigenschaft setzen.

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

Entfernen

Im Gegensatz zu pop und unshift entfernt die remove-Funktion den Knoten um den angegebenen Index. Überprüfen Sie wie üblich, ob der Index gültig ist. Wenn der Index der Länge 1 oder 0 entspricht, verwenden Sie pop oder shift . Andernfalls erhalten wir den Knoten am Index-1, Setzen Sie die nächste Eigenschaft auf diesem Knoten auf die nächste der nächsten Eigenschaft, danach dekrementieren wir die Größe.

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

Rückwärts

Die ultimative umgekehrte Frage! Wie kehren wir die Liste um? Zuerst tauschen wir head und Tail aus, deklarieren next und previous , setzen das previous als null . Wir durchlaufen die Liste.

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