JavaScript implementiert eine einzelne verknüpfte Listenprozessanalyse

Vorwort:

Zum Speichern mehrerer Elemente sind Arrays die am häufigsten verwendete Datenstruktur. Allerdings haben Arrays auch viele Nachteile:

• Für die Erstellung eines Arrays ist normalerweise ein kontinuierlicher Speicherplatz erforderlich, und die Größe ist festgelegt. Wenn das aktuelle Array die Kapazitätsanforderungen nicht erfüllen kann, muss es erweitert werden (normalerweise durch Beantragen eines größeren Arrays und anschließendes Kopieren der Elemente im ursprünglichen Array dorthin).
• Das Einfügen von Daten am Anfang oder in der Mitte eines Array-Elements ist sehr aufwändig und erfordert das Verschieben einer großen Anzahl von Elementen.

Um mehrere Elemente zu speichern, ist eine verknüpfte Liste eine weitere Option. Im Gegensatz zu einem Array müssen die Elemente in einer verknüpften Liste keinen zusammenhängenden Speicherplatz im Speicher bilden. Jedes Element einer verknüpften Liste hat einen Knoten, der das Element selbst und einen Verweis auf das nächste Element speichert.
Verkettete Listen haben gegenüber Arrays einige Vorteile:

• Der Speicherplatz muss nicht zusammenhängend sein, wodurch der Computerspeicher voll ausgenutzt und eine flexible dynamische Speicherverwaltung erreicht werden kann.
• Die Größe verknüpfter Listen muss bei ihrer Erstellung nicht festgelegt werden und sie können unbegrenzt erweitert werden.
• Beim Einfügen und Löschen von Daten in eine verknüpfte Liste kann die Ereigniskomplexität O(1) erreichen, was viel effizienter ist als ein Array.

Verkettete Listen haben gegenüber Arrays einige Nachteile:

• Beim Zugriff auf ein Element an einer beliebigen Position in einer verknüpften Liste muss am Anfang begonnen werden. Auf das Element kann nicht direkt über den Index zugegriffen werden.

1. Was ist eine einfach verknüpfte Liste

Was genau ist also eine einfach verkettete Liste?

Es ist wie bei einem Zug. Die Lokomotive ist mit einem Knoten verbunden, auf dem Knoten befinden sich Passagiere, und dieser Knoten ist mit dem nächsten Knoten verbunden usw., wie unten dargestellt:

Unsere verknüpfte Listenstruktur ist:

Nachdem wir nun die intuitiv verknüpfte Liste verstehen, kapseln wir den Code für die einfach verknüpfte Liste.

2. Kapselung einer einfach verknüpften Liste

Zuerst kapseln wir eine NodeList 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 (Daten und einen Verweis auf den nächsten Knoten). Dann speichern wir zwei Attribute in NodeList Klasse, eines ist die Länge der verknüpften Liste und das andere ist der Kopfknoten in der verknüpften Liste.

Wie unten dargestellt:

 Funktion LinkedList(){
            diese.Länge = 0;
            dieser.kopf = null;
            //Interne Klassenfunktion Node(data){
                diese.daten = Daten;
                dies.nächstes = null;
            }
        }

3. Allgemeine Operationen einfach verknüpfter Listen

Fügen Sie dann die häufig verwendeten Operationen einfach verketteter Listen hinzu. Die wichtigsten sind:

• append（element) : Fügt 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 length 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.

Als nächstes werden wir sie nacheinander implementieren.

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

Weil es zwei mögliche Situationen gibt, Daten am Ende einer verknüpften Liste hinzuzufügen:

• Die verknüpfte Liste selbst ist leer und die neu hinzugefügten Daten sind der einzige Knoten
• Die verknüpfte Liste ist nicht leer und Knoten müssen nach anderen Knoten hinzugefügt werden

Wir müssen also eine Entscheidung treffen: Wenn die verknüpfte Liste leer ist, richten Sie den Zeiger des Kopfknotens direkt auf den neuen Knoten.
Wenn die verknüpfte Liste nicht leer ist, erstellen Sie einen temporären Knoten, machen Sie ihn gleich dem Kopfknoten und beurteilen Sie ihn. Wenn das Zeigerfeld des Knotens, auf den er zeigt, leer ist, handelt es sich um den Endknoten. Fügen Sie den neu hinzugefügten Knoten am Ende hinzu, d. h. lassen Sie den Zeiger des Endknotens auf den neu hinzugefügten Knoten zeigen. Wenn das Zeigerfeld des Knotens, auf den es zeigt, nicht leer ist, lassen Sie das Zeigerfeld dieses temporären Knotens auf den nächsten Knoten zeigen und führen Sie die Schleife weiter aus, bis das Zeigerfeld dieses Knotens leer ist (dh der Endknoten). Erhöhen Sie dann jedes Mal, wenn Sie einen Knoten hinzufügen, die Länge der verknüpften Liste um 1.

LinkedList.prototype.append = Funktion(Daten){
                var newNode = neuer Knoten (Daten);
                // Bestimmen Sie, ob die verknüpfte Liste leer ist // 1. Wenn sie leer ist if (this.length === 0) {
                    dieser.kopf = neuer Knoten;
                }anders{
                    //Nicht leer var current = this.head;
                    wenn(aktuell.nächste){
                        aktuell = aktuell.nächstes;
                    }
                    aktuell.nächster = neuer Knoten;
                }
                diese.Länge += 1;
            }

2. toString-Methode ----- gibt den Wert des Elements aus

Das ist relativ einfach. Die Hauptsache ist, jedes Element abzurufen. Da das Abrufen eines beliebigen Elements der verknüpften Liste beim ersten Knoten beginnen muss, können wir beim Kopfknoten beginnen, jeden Knoten durchlaufen, element herausnehmen, es zu einer Zeichenfolge verketten und die Zeichenfolge zurückgeben.

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

Überprüfung: Mehrere neue Knoten erstellen und drucken

 var list = neue LinkedList();
        Liste.anhängen('a');
        list.append('b');
        list.append('c');
        Liste.anhängen('d');
        Liste.anhängen('e');
        Alarm (Liste);

Das Druckergebnis ist:

3. Einfügemethode ----- Fügt ein Element an einer bestimmten Position in der Liste ein

Um die Methode zum Einfügen von Daten an einer beliebigen Position zu implementieren, bestimmen Sie zunächst, ob die Einfügeposition außerhalb der Grenzen liegt, und teilen Sie sie dann in zwei Fälle auf, wenn sie nicht außerhalb der Grenzen liegt. Wenn es an der ersten Position eingefügt wird, bedeutet dies, dass der neu hinzugefügte Knoten der Kopf ist. Dann muss der ursprüngliche Kopfknoten als nächster des neuen Knotens verwendet werden, und dann muss der Kopf auf den neuen Knoten zeigen. Wenn Sie es an anderen Positionen einfügen, müssen Sie zuerst die Knotenposition durch eine Schleife finden und während der Schleife den vorherigen und den nächsten Knoten speichern. Nachdem Sie die richtige Position gefunden haben, richten Sie Next des neuen Knotens auf den nächsten Knoten und next Knoten des vorherigen Knotens auf den neuen Knoten.

Der Code lautet wie folgt:

 LinkedList.prototype.insert = Funktion(Position,Daten){
                wenn(Position<0 || Position >diese.Länge){
                   gibt false zurück;
               }
                var newNode = neuer Knoten (Daten);
                Var-Index = 0;
              wenn(Position == 0){
                neuerKnoten.nächster = dieser.Kopf;
                dieser.kopf = neuer Knoten;

              }anders{
                    während(index++ < position){
                        var aktuell = dieser.kopf;
                        var vorherige = null;
                        vorherige = aktuelle;
                        aktuell = aktuell.nächstes;
                    }
                    neuerNode.next = aktuell;
                    vorheriger.nächster = neuer Knoten;
                }
                diese.Länge += 1;
                gibt true zurück;
                }

Überprüfung: Tragen Sie an der ersten Stelle xl und an der zweiten Stelle wh ein.

Liste.Einfügen(1,'xl')
       Liste.Einfügen(2,'wh')
        Alarm (Liste)

4. Get-Methode ----- Holen Sie sich das Element an der entsprechenden Position

Diese Methode ist relativ einfach. Zuerst wird geprüft, ob positon außerhalb der Grenzen liegt. Anschließend wird die verknüpfte Liste über temporäre Knoten durchlaufen, bis die Zielposition erreicht ist, und das Element an dieser Position abgerufen.

LinkedList.prototype.get = Funktion(Position,Daten){

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

Überprüfung: Holen Sie sich das Element an der dritten Position:

alarm(Liste.get(3));

5. indexOf()-Methode ----- gibt den Index eines Elements in einer Liste zurück

Stellen Sie zunächst fest, ob die Position des gesuchten Elements vorhanden ist. Wenn nicht, geben Sie -1 zurück. Wenn es vorhanden ist, gibt es zwei Fälle: Wenn das zurückgegebene Element an der ersten Position steht, wird direkt der Index der ersten Position zurückgegeben. Wenn sich das zurückgegebene Element an einer anderen Position befindet, müssen Sie zunächst die Knotenposition über eine Schleife finden. Während dieses Vorgangs muss der Index um die Anzahl der Durchläufe erhöht werden. Nachdem die Position des richtigen Elements gefunden wurde, ist der ausgegebene Index die Zielposition.

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

Überprüfung: Ermitteln Sie den Index von c:

Alarm(Liste.Index von('c'));

6. Aktualisierungsmethode ----- Ändern Sie das Element an einer bestimmten Position

Diese Methode ist der get-Methode sehr ähnlich. Sie durchläuft sie rückwärts. Wenn der Wert von index gleich position ist, bedeutet dies, dass die Zielposition gefunden wurde und das Datum auf den Zielwert geändert wurde:

LinkedList.prototype.update = Funktion(Position,Element){
                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 = ele;
                    gibt true zurück;
                }
            }

Überprüfung: Ändern Sie das Element an Position 0 in: bear

 Liste.Update(0,'Bär')
      Alarm (Liste)

7. removeAt-Methode ----- Entfernt ein Element von der angegebenen Position der Liste

Bestimmen Sie zunächst, ob die Position des gelöschten Elements außerhalb der Grenzen liegt. Wenn sie dann nicht außerhalb der Grenzen liegt, geben Sie zwei temporäre Knoten an, previous und current . previous wird verwendet, um den Wert von previous current zu speichern. Beginnen Sie mit der Durchquerung vom Kopfknoten, bis die Indexposition der Zielposition entspricht. Lassen Sie den temporären Knoten current zur Zielposition durchlaufen und lassen Sie das previous next des temporären Knotens auf das next next zeigen.

LinkedList.prototype.removeAt = Funktion (Position, Daten) {
                var aktuell = dieser.kopf;
                var vorherige = null;
                Var-Index = 0;
                wenn(Position<0 || Position>=diese.Länge){
                    gibt false zurück;
                }anders{
                    während(index++ <position){
                        vorherige = aktuell;
                        aktuell = aktuell.nächstes;
                    }
                    vorheriges.nächstes = aktuelles.nächstes;
                    diese.Länge -= 1;
                    gibt true zurück;
                }
            }
        }

Überprüfung: Entfernen Sie das Element an der dritten Position:

Liste.entfernenAt(3)
      Alarm (Liste)

8. Remove-Methode - Entfernen Sie ein Element aus der Liste

Bestimmen Sie zunächst, ob das zu löschende Element in der verknüpften Liste enthalten ist. Wenn nicht, geben Sie false zurück. Andernfalls erstellen Sie einen temporären Knoten zum Durchlaufen der verknüpften Liste. Wenn der Datenwert des temporären Knotens dem zu löschenden Element entspricht, beenden Sie das Durchlaufen und lassen Sie das vorherige next des temporären Knotens auf das nächste nächste Element zeigen. Hier können Sie einen temporären Knoten erstellen, um den vorherigen current Wert zu speichern.

LinkedList.prototype.remove = Funktion(Element){
                var aktuell = dieser.kopf;
                var vorherige = null;
                Var-Index = 0;
                während(aktuelle.Daten !== ele){
                    vorherige = aktuelle;
                    aktuell = aktuell.nächstes;
                    Index++;
                }
                vorheriges.nächstes = aktuelles.nächstes;
            }

Überprüfung: Löschen Sie das Element mit dem Wert xl:

 Liste.entfernen('xl')
      Alarm (Liste)

9. isEmpty-Methode ----- Bestimmen Sie, ob die verknüpfte Liste leer ist

Gemäß length wird true zurückgegeben, wenn die verknüpfte Liste keine Elemente enthält, und false, wenn die Länge der verknüpften Liste größer als 0 ist

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

verifizieren:

 Alarm (Liste.istEmpty())

9. Size-Methode ----- Gibt die Anzahl der in der verknüpften Liste enthaltenen Elemente zurück

length des direkt zurückgegebenen Elements ist seine Nummer.

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

verifizieren:

   Alarm (Liste.Größe ())

Dies ist das Ende dieses Artikels über JavaScript, das die Prozessanalyse von Single Linked Lists implementiert. Weitere relevante Inhalte zu JavaScript, das Single Linked Lists implementiert, finden Sie in den vorherigen Artikeln von 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!