JavaScript implementiert eine doppelt verknüpfte Liste (Codebeispiel)

In diesem Artikel stellen wir Ihnen vor, wie Sie eine doppelt verknüpfte Liste in JavaScript implementieren. Wir hoffen, dass er Freunden in Not hilfreich sein wird!

Was ist eine doppelt verknüpfte Liste?

In einer doppelt verknüpften Liste hat jeder Knoten einen Verweis auf den vorherigen Knoten und den nächsten Knoten. Der vorherige und nächste Start- und Endknoten sollten auf Null zeigen.

Implementierung einer doppelt verknüpften Liste

Im folgenden Code erstellen wir eine Hilfsklasse Node , das drei Attributdaten enthält: prev, next.

class Node {

  constructor(data){
    this.data = data; // data
    this.prev = null; // 引用prev节点
    this.next = null; // 引用next节点
  }}

Daten: Die Daten, die wir dem Knoten hinzufügen müssen.

prev: bezieht sich auf den vorherigen Knoten.

next: bezieht sich auf den nächsten Knoten.

Der Hauptalgorithmus beginnt

class DoublyLinkedList{

   constructor(){
        this.head = null;
        this.tail = null;
        this.length = null;
  }}

Im obigen Code erstellen wir eine DoublyLinkedList-Klasse mit drei Eigenschaften: Kopf, Schwanz und Länge.

Kopf: Es ist der erste Knoten in der Liste.

tail: Der letzte Knoten in der Liste.

Länge: Wie viele Knoten gibt es in der Liste?

Fügen wir diese Funktionen zu unserer doppelt verknüpften Liste hinzu

Push-Methode

Push-Methode hilft uns, neue Knoten am Ende der verknüpften Liste hinzuzufügen.

push(data){

    const node = new Node(data);

    if(!this.head){
      this.head = node;
      this.tail = node;
    }else{
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;

    }

    this.length++;
  }

1. Im obigen Code deklarieren wir zunächst eine neue Variable und rufen den Knotenkonstruktor auf.

2. Wenn es keinen this.head gibt, sind this.head und this.tail die neuen Knoten, die wir in Schritt 1 erstellt haben.

3. Wenn bereits ein Knoten vorhanden ist

sollte das neue Attribut node.prev this.tail sein

this.tail.next sollte ein neuer Knoten sein

Schwanz aktualisieren.

4. Erhöhen Sie die Länge um 1.

Pop-Methode

hilft uns, den letzten Knoten aus der Liste zu entfernen.

In einer doppelt verknüpften Liste ist es einfach, den letzten Knoten aus der Liste zu entfernen, da im Tail-Attribut ein Verweis auf den vorherigen Knoten vorhanden ist.

pop(){

    if(!this.head) return null

    // tail是最后一个节点，因此我们从tail中提取prev属性
    const prevNode = this.tail.prev    
    if(prevNode){
       prevNode.next = null;
       this.tail = prevNode; // 更新tail
    }else{
      // 如果prev属性为null，则表示只有一个节点
      this.head = null;
      this.tail = null;
    }
     this.length--; 
  }

1. Im obigen Code deklarieren wir zunächst eine neue Variable und speichern das vorherige Attribut von tail.

2. Wenn der vorherige Knoten gefunden wird.

Letzten Knoten löschen

Ende aktualisieren.

3. Wenn der vorherige Knoten leer ist, bedeutet das, dass es nur einen Knoten gibt

this.head und this.tail sollten null sein.

4. Reduzieren Sie die Länge um 1.

insertBeginning

insertBeginning-Methode hilft uns, einen neuen Knoten am Anfang der Liste einzufügen.

insertBeginning(data){

    // 创建新节点
    const node = new Node(data);

    // 如果没有节点
    if(!this.head) {
      this.head = node;
      this.tail = node;
    }else{
      this.head.prev = node
      node.next = this.head;
      this.head = node;
    }
    // 增加长度
    this.length++;

  }

removeFirst-Methode

removeFirst-Methode hilft uns, den ersten Knoten aus der verknüpften Liste zu löschen.

removeFirst(){

    if(!this.head) return null

    // 存储第二个节点
    const node = this.head.next;

    if(node){
     // 删除前一个节点
      node.prev = null
     // 更新head
      this.head = node    
      }else{
      // 只有一个节点，所以我们将head和tail更新为null
      this.head = null
      this.tail = null
    }
     this.length--;

  }

Verwandte Empfehlungen: „Javascript-Tutorial“

Das obige ist der detaillierte Inhalt vonJavaScript implementiert eine doppelt verknüpfte Liste (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!