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 .

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.

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.

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.

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.

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.

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.

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.

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.

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.