JavaScript implementiert eine bidirektionale verknüpfte Listenprozessanalyse

1. Was ist eine doppelt verknüpfte Liste

Wir wissen, dass eine einfach verknüpfte Liste nur von Anfang bis Ende oder von Ende zu Anfang (im Allgemeinen von Anfang bis Ende) durchlaufen werden kann, d. h. der Prozess des Verbindens der verknüpften Listen erfolgt nur in eine Richtung, und das Implementierungsprinzip besteht darin, dass in der vorherigen verknüpften Liste ein Verweis auf die nächste vorhanden ist. Es hat einen offensichtlicheren Nachteil:

Wir können den nächsten Knoten leicht erreichen, aber es ist schwierig, zum vorherigen Knoten zurückzukehren. Bei der tatsächlichen Entwicklung stoßen wir jedoch häufig auf Situationen, in denen wir zum vorherigen Knoten zurückkehren müssen, sodass hier eine bidirektionale verknüpfte Liste erforderlich ist.

Die sogenannte doppelt verknüpfte Liste ist eine verknüpfte Liste, die von Anfang bis Ende und von Ende bis Anfang durchlaufen werden kann. Die doppelt verknüpfte Liste hat jedoch auch Nachteile. Beispielsweise müssen bei jedem Einfügen oder Löschen eines Knotens vier Knotenreferenzen verarbeitet werden, statt zwei. Im Vergleich zu einer einfach verknüpften Liste benötigt sie mehr Speicher. Diese Nachteile sind jedoch im Vergleich zum Komfort unserer Nutzung vernachlässigbar.
Schauen wir uns das Strukturdiagramm einer doppelt verketteten Liste an. Wie unten dargestellt:

Merkmale einer doppelt verketteten Liste:

• Sie können einen Kopf und einen Schwanz verwenden, um jeweils auf den Kopf- und den Schwanzknoten zu verweisen.
• Jeder Knoten besteht aus drei Teilen: dem Zeiger auf den vorherigen Knoten (prev), dem gespeicherten Element (data) und dem Zeiger auf den nächsten Knoten (next).
• Der vorherige Knoten des ersten Knotens einer doppelt verknüpften Liste ist null
• Der nächste oder letzte Knoten einer doppelt verketteten Liste ist null

Wir können es wie folgt abstrahieren:

Nachdem wir die Struktur einer doppelt verketteten Liste kennen, schauen wir uns die Kapselung einer doppelt verketteten Liste an.

2. Kapselung einer doppelt verknüpften Liste

Zuerst kapseln wir eine DoublyLinkedList -Klasse, um die Struktur der verknüpften Liste darzustellen. In dieser Klasse kapseln wir eine innere Klasse Node , um die Informationen zu jedem Knoten zu kapseln (Verweis auf den vorherigen Knoten, Daten und Verweis auf den nächsten Knoten). Dann speichern wir drei Attribute in Node Klasse, eines ist die Länge der verknüpften Liste, eines ist der Kopfknoten in der verknüpften Liste und eines ist der Endknoten der verknüpften Liste. Wie unten dargestellt:

Funktion Doppelt verknüpfte Liste () {
	 dieser.kopf = null;
	 dies.tail = null;
	 diese.Länge = 0;
	 Funktion Knoten(Daten){
		 diese.daten = Daten;
		 dies.prev = null;
		 dies.nächstes = null;
	}
 

3. Allgemeine Operationen bidirektionaler verknüpfter Listen

Anschließend können Sie allgemeine Operationen für bidirektional verknüpfte Listen hinzufügen:

append（element : füge ein Element am Ende der Liste hinzu

insert(position,element) : fügt ein Element an einer bestimmten Position in einer Liste ein

get(position) : Holt das Element an der entsprechenden Position

indexOf(element) : Gibt den Index eines Elements in der Liste zurück, oder -1, wenn das Element nicht in der Liste existiert

update(position，ele) : Ändert das Element an einer bestimmten Position

removeAt(position) : Entfernt ein Element von der angegebenen Position in der Liste.

remove(element) : Entfernt ein Element aus der Liste

isEmpty() : Gibt true zurück, wenn die verknüpfte Liste keine Elemente enthält, und false, wenn die Länge der verknüpften Liste größer als 0 ist.

size() : Gibt die Anzahl der Elemente in der verknüpften Liste zurück, die mit der Längeneigenschaft des Arrays zusammenhängt

toString() : Da das Listenelement die Node-Klasse verwendet, müssen Sie die vom JavaScript-Objekt geerbte Standardmethode toString überschreiben, um den Wert des Elements auszugeben.

forwardString() : Gibt die Knotenstringform der Vorwärtsdurchquerung zurück

backwardString() : Gibt die Zeichenfolge des rückwärts durchlaufenen Knotens zurück

Als nächstes werden wir sie nacheinander implementieren.

1. append(element)-Methode ----- fügt ein Element am Ende der Liste hinzu

Diese Methode ähnelt der Methode mit einfach verknüpften Listen. Erstellen Sie zunächst eine neue Liste und ermitteln Sie dann, ob die verknüpfte Liste leer ist. Wenn sie leer ist, lassen Sie den Kopf der verknüpften Liste direkt auf die neu erstellte verknüpfte Liste verweisen. Wenn es nicht leer ist, lassen Sie den Vorgängerzeiger des neuen Knotens auf das Ende der verknüpften Liste zeigen, und der Knoten am Ende der verknüpften Liste zeigt auf die neue verknüpfte Liste.

Doubly.prototype.append = Funktion(Daten){
                var newNode = neuer Knoten (Daten);
                wenn(diese.Länge == 0){
                    dieser.kopf = neuer Knoten;
                }anders{
                    neuerNode.prev = dieser.tail;
                    this.tail.next = neuer Knoten;
                    }
                this.tail = neuer Knoten;
                diese.Länge += 1;
            }

2. Konvertieren Sie die verknüpfte Liste in eine Zeichenfolge

1. toString(): gibt den Wert des Elements in Vorwärtsrichtung aus

Diese Methode wird hauptsächlich verwendet, um jedes Element abzurufen. Standardmäßig muss jedes Element der verknüpften Liste beim ersten Knoten beginnen. Daher können wir beim Kopfknoten beginnen, jeden Knoten durchlaufen, das Element herausnehmen, es zu einer Zeichenfolge verketten und die Zeichenfolge zurückgeben. Die konkrete Methode besteht darin, einen temporären Knoten current zu erstellen, diesen temporären Knoten auf den Kopf der doppelt verknüpften Liste zeigen zu lassen und dann der Reihe nach rückwärts bis zum next Zeiger zu durchlaufen und dabei die bei jedem Durchlauf erhaltenen Daten zusammenzufügen.

DoublyLinkedList.prototype.tostring = Funktion(){
                var aktuell = dieser.kopf;
                var str = '';
                während(aktuell){
                    str += aktuelle.Daten + ' ';
                    aktuell = aktuell.nächstes;
                }
               gibt str zurück;
            }

2. forwardString(): Gibt die Knotenstringform der Vorwärtsdurchquerung zurück

Diese Methode implementiert auch den Vorwärtsdruck und die Ausgabe einer bidirektional verknüpften Liste, sodass wir die vorherige Methode hier direkt aufrufen können:

DoublyLinkedList.prototype.forwardString = Funktion(){
               gib dies zurück.toString()
            }

3. backwardString(): Gibt die Knotenstringform der umgekehrten Durchquerung zurück

Diese Methode durchläuft die einzelnen Elemente hauptsächlich von hinten nach vorne, um sie abzurufen und auszudrucken. Wir können also beim Endknoten beginnen, jeden Knoten durchlaufen, das Element herausnehmen, es zu einer Zeichenfolge verketten und die Zeichenfolge zurückgeben. Die konkrete Methode besteht darin, einen temporären Knoten current zu erstellen, diesen temporären Knoten auf das Ende der doppelt verknüpften Liste zeigen zu lassen und dann der Reihe nach vorwärts durch den prev Zeiger zu durchlaufen und die bei jedem Durchlauf erhaltenen Daten zusammenzufügen.

 DoublyLinkedList.prototype.backwardString = Funktion(){
                var aktuell = dies.tail;
                var str = '';
                //Der Reihe nach vorwärts gehen und jeden Knoten abrufen while(current){
                    str += aktuelle.Daten +' ';
                    aktuell = aktuell.vorherige;
                }
                gibt str zurück;
            }

verifizieren:

Beispielsweise verwenden wir append() , um eine doppelt verknüpfte Liste mit drei Daten zu erstellen und diese dann vorwärts bzw. rückwärts zu verketten:

var list = neue Doppelt verknüpfte Liste ();
         Liste.anhängen("a");
         list.append("b");
         list.append("c");
         Liste.anhängen("d");
         console.log('toString()-Methode: ' + list.toString());
         console.log('forwardString()-Methode: '+list.forwardString());
         console.log('backwardString()-Methode: ' + list.backwardString());

Das Druckergebnis ist:

Überprüfung erfolgreich.

3. insert(position,element): Fügt ein Element an einer bestimmten Position in einer Liste ein

Diese Methode ist relativ kompliziert. Bestimmen Sie zunächst, ob die einzufügende Position außerhalb der Grenzen liegt. Wenn sie nicht außerhalb der Grenzen liegt, beurteilen Sie dies anhand der Situation der verknüpften Liste. Wenn die verknüpfte Liste leer ist, ist der eingefügte Knoten das erste Element und die Zeiger des Kopfknotens und des Endknotens zeigen direkt auf den neu erstellten Knoten. Wenn die verknüpfte Liste nicht leer ist, gibt es drei Situationen für die Einfügeposition: Einfügen an der ersten Position, Einfügen am Ende und Einfügen in der Mitte. Die spezifischen Vorgänge sind wie folgt:

DoublyLinkedList.prototype.insert = Funktion(Position,Daten){
        var newNode = neuer Knoten (Daten);
         // Urteil außerhalb der Grenzen. Wenn es nicht erfüllt ist, wird „false“ zurückgegeben.
         wenn(Position<0 || Position>diese.Länge){
             gibt false zurück;
         }anders{
             //Nochmals beurteilen//Wenn die verknüpfte Liste leer ist, fügen Sie direkt if(position==0){ ein.
                 dieser.kopf = neuer Knoten;
                 this.tail = neuer Knoten;
             }anders {
             //Wenn die verknüpfte Liste nicht leer ist //Wenn die Einfügeposition am Ende ist if(position == this.length){
                     this.tail.next = neuer Knoten;
                     neuerNode.prev = dieser.tail;
                     this.tail = neuer Knoten;
                 }sonst wenn(Position == 0){
                     //Wenn die Einfügeposition der erste Knoten ist, this.head.prev = newNode;
                     neuerKnoten.nächster = dieser.Kopf;
                     dieser.kopf = neuer Knoten;
                 }anders{
                     //Wenn die Einfügeposition in der Mitte ist, var index = 0;
                     var aktuell = dieser.kopf;
                     während(index++ <position){
                         aktuell = aktuell.nächstes;
                     }
                         neuerNode.next = aktuell;
                         neuerNode.prev = aktuell.prev;
                         aktuell.vorheriger.nächster = neuer Knoten;
                         current.prev = neuer Knoten;
                 
             }
             diese.Länge += 1;
         }
        
     }
 }

Überprüfung: Wenn Sie xl an Position 1 einfügen, wie unten gezeigt:

Liste.Einfügen(1,'xl')
Konsole.log(Liste.toString());

Die laufenden Ergebnisse sind:

Überprüfung erfolgreich.

4. get(position): Holt das Element an der entsprechenden Position

Diese Methode ermittelt zunächst, ob die Position außerhalb der Grenzen liegt. Wenn sie nicht außerhalb der Grenzen liegt, werden ein temporärer Knoten und ein Index definiert und der Zeiger des temporären Knotens wird so eingestellt, dass er auf den Kopfknoten zeigt. Der temporäre Knoten wird durchlaufen und der Index wird erhöht. Wenn die Position des durchlaufenen Knotens der Position des abzurufenden Elements entspricht, ist das Element an der entsprechenden Position des temporären Knotens das abzurufende Element.

DoublyLinkedList.prototype.get = Funktion(Position){
        
        wenn(Position<0 || Position>=diese.Länge){
            gibt false zurück;
        }anders{
            Var-Index = 0;
            var aktuell = dieser.kopf;
            während(index++ <position){
                aktuell = aktuell.nächstes;
            }
            aktuelle Daten zurückgeben;
        }
    }

Überprüfung: Abfrage des Elements mit Position = 2

console.log('list.get(2):'+list.get(2));

Das Ergebnis ist:

Überprüfung erfolgreich.

Diese Suchmethode hat jedoch einen Nachteil: Sie kann nur von vorne nach hinten suchen, was in einigen Fällen sehr ineffizient ist. Daher können wir von beiden Enden aus suchen. Die spezifische Suchmethode lautet: Wenn die Position des Knotens, den wir finden möchten, kleiner oder gleich der halben Länge der verknüpften Liste ist, können wir von vorne nach hinten suchen. Wenn die Position des zu findenden Knotens größer als die halbe Länge ist, suchen wir von hinten nach vorne. Der Implementierungscode lautet:

    DoublyLinkedList.prototype.get = Funktion(Position){
        
        wenn(Position<0 || Position>=diese.Länge){
            gibt false zurück;
        }anders{
            var Länge = Math.floor(this.length/2);
            wenn(Position<=Länge){
                Var-Index = 0;
                var aktuell = dieser.kopf;
                während(index++ <position){
                 aktuell = aktuell.nächstes;
                }
            }anders{
                var index = diese.Länge-1;
                var aktuell = dies.tail;
                während(Index->Position){
                    aktuell = aktuell.vorherige;
                }
            }
            aktuelle Daten zurückgeben;
        }
    }

5. indexOf(element): gibt den Index des Elements in der Liste zurück

Erstellen Sie einen temporären Knoten und Index, lassen Sie den temporären Knoten auf den Kopfknoten zeigen, durchlaufen Sie ihn der Reihe nach rückwärts und lassen Sie den Index zunehmen. Wenn das vom durchlaufenen temporären Knoten erhaltene Element dem von uns angegebenen Element entspricht, ist die Position des temporären Knotens zu diesem Zeitpunkt unsere Zielposition und der Index dieser Position ist der Index des Zielwerts.

DoublyLinkedList.prototype.indexOf = Funktion(Daten){
        var aktuell = dieser.kopf;
        Var-Index = 0;
        während(aktuell){
            wenn (aktuelle.Daten === Daten) {
            Rückgabeindex;
         }
         aktuell = aktuell.nächstes;
         Index++;
        }
        Rückgabe -1;
    }

Überprüfung erfolgreich.

6. update(position, ele): Ändere das Element an einer bestimmten Position

Bestimmen Sie zunächst, ob die zu ändernde Position außerhalb der Grenzen liegt. Wenn sie nicht außerhalb der Grenzen liegt, definieren Sie einen temporären Knoten und einen Index. Lassen Sie den temporären Knoten auf den Kopfknoten zeigen, die Indexposition ist 0. Durchlaufen Sie den temporären Knoten und bestimmen Sie, ob der Index des temporären Knotens zu diesem Zeitpunkt der Position des zu ändernden Elements entspricht. Wenn sie gleich sind, ist die Position des temporären Knotens zu diesem Zeitpunkt die Position des zu ändernden Elements, und das Element kann direkt im Datenbereich des temporären Knotens geändert werden.

DoublyLinkedList.prototype.update = Funktion(Position,neueDaten){
        wenn(Position<0 || Position>=diese.Länge){
            gibt false zurück;
        }anders{
            Var-Index = 0;
            var aktuell = dieser.kopf;
            während(index++ <position){
                aktuell = aktuell.nächstes;
            }
            aktuelle.Daten = neueDaten;
            gibt true zurück;
        }
    }

Überprüfung: Ersetzen Sie die Daten an Position 0 rc

Liste.Update(0,'rc')
       console.log("list.update(0,'rc') ist:");
       Konsole.log(Liste.toString());

Überprüfung erfolgreich.

7. removeAt(position): Entfernt ein Element von der angegebenen Position der Liste

Diese Methode ähnelt der insert() -Methode, indem sie zunächst ermittelt, ob die Grenzen überschritten wurden. Wenn die Grenzen nicht überschritten wurden und nur ein Knoten in der verknüpften Liste vorhanden ist, wird das Element direkt entfernt, sodass sowohl der Kopfknoten als auch der Endknoten der verknüpften Liste auf leer zeigen. Wenn die verknüpfte Liste mehrere Knoten hat, kann sie in drei Fälle unterteilt werden. Die Vorgänge sind wie folgt:

DoublyLinkedList.prototype.removeAt = Funktion(Position){
        wenn(Position<0 || Position>=diese.Länge){
            gibt null zurück;
        }anders{
            var aktuell = dieser.kopf;
            wenn(diese.Länge === 1){
            //Die Länge der verknüpften Liste beträgt 1
                dieser.kopf = null;
                this.tail = null
            }else{//Die Länge der verknüpften Liste ist nicht 1
                wenn(Position === 0){
                //Erste Stelle löschen this.head.next.prev = null;
                    dieser.Kopf = dieser.Kopf.Nächster;
                }sonst wenn(Position === diese.Länge-1){
                    dies.tail.prev.next = null;
                    dies.tail = dies.tail.prev;
                }anders{
                    Var-Index = 0;
                    während(index++ <position){
                        aktuell = aktuell.nächstes;
                    }
                    aktuell.vorheriges.nächstes = aktuell.nächstes;
                    aktuell.nächstes.vorherig = aktuell.vorherig;
                }
            }
            diese.Länge -=1;
            aktuelle Daten zurückgeben;
        }
    }

Überprüfung: Löschen Sie die Daten an Position 3:

Liste.entfernenAt(3)
       console.log("list.removeAt(3) ist:");
       Konsole.log(Liste.toString());

Das Ergebnis ist:

Überprüfung erfolgreich

8. remove(element): Entferne ein Element aus einer Liste

Sie können die Position eines Elements in der verknüpften Liste direkt gemäß indexOf(element) abrufen und es dann gemäß removeAt(position) löschen.

 DoublyLinkedList.prototype.remove = Funktion(Daten){
        var index = this.indexOf(Daten);
        gib dies zurück.removeAt(index);
    }

Überprüfung: Löschen Sie den Knoten, dessen Daten rc sind:

Liste.entfernen('rc');
       console.log("list.remove('rc') ist:");
       Konsole.log(Liste.toString());

9. isEmpty (): Bestimmen Sie, ob die verknüpfte Liste leer ist

Bestimmen Sie direkt, ob die Anzahl der Elemente in der verknüpften Liste Null ist. Wenn sie Null ist, ist sie leer und gibt „true“ zurück. Andernfalls ist sie nicht leer und gibt „false“ zurück.

DoublyLinkedList.prototype.isEmpty = Funktion(){
        gib diese Länge zurück == 0;
    }
    

verifizieren:

console.log("Ist die verknüpfte Liste leer: "+list.isEmpty());     

10. size(): Gibt die Anzahl der in der verknüpften Liste enthaltenen Elemente zurück

Die Länge einer verknüpften Liste ist die Anzahl der Elemente.

DoublyLinkedList.prototype.size = Funktion(){
        gib diese Länge zurück;
    }

verifizieren:

 console.log("Die Anzahl der Elemente in der verknüpften Liste ist: "+list.size());

Oben sind die Details der Implementierung der bidirektionalen verknüpften Liste in JavaScript aufgeführt. Weitere Informationen zur bidirektionalen verknüpften Liste in JavaScript finden Sie in den anderen verwandten Artikeln auf 123WORDPRESS.COM!