Detaillierte Einführung in verknüpfte Listen in JavaScript

Dieser Artikel bietet Ihnen eine detaillierte Einführung in verknüpfte Listen in JavaScript. Ich hoffe, dass er für Freunde hilfreich ist.

Verknüpfte Listen und Arrays

Jeder hat Arrays in js verwendet. Arrays sind eigentlich eine sequentielle Speicherstruktur linearer Tabellen. Ihr Merkmal ist, dass sie eine Reihe von Adressen verwendet . Aufeinanderfolgende Speicherzellen speichern nacheinander Datenelemente. Seine Mängel sind auch auf seine Eigenschaften zurückzuführen. Beispielsweise muss beim Löschen oder Einfügen eines Arrays möglicherweise eine große Anzahl von Elementen verschoben werden.

Hier ist eine grobe Simulation des Einfügevorgangs des Arrays:

    insert(arr, index, data){
        for(let i = index + 1; i <p> Aus dem obigen Code können wir erkennen, dass das Einfügen und Löschen des Arrays ein O(n)-Vorgang sein kann . Dies führt dazu, dass die Datenstruktur der verknüpften Liste nicht erfordert, dass logisch benachbarte Elemente an physischen Orten benachbart sind, sodass sie nicht die Mängel der sequentiellen Speicherstruktur aufweist Array in einem kontinuierlichen Raum. Vorteile des Zugriffs. </p><h3 id="Einseitig-verknüpfte-Liste">Einseitig verknüpfte Liste</h3><p><span class="img-wrap"><img src="/static/imghw/default1.png" data-src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" class="lazy" title="1546394138978971.png" alt="Detaillierte Einführung in verknüpfte Listen in JavaScript"></span></p><h4 id="Funktionen-der-einseitig-verknüpften-Liste">Funktionen der einseitig verknüpften Liste: </h4>

• Verwenden Sie einen beliebigen Speicherplatz zum Speichern von Datenelementen (der Speicherplatz kann hier kontinuierlich oder diskontinuierlich sein)

• Jeder Knoten (Knoten) besteht aus den Daten selbst und einem Zeiger auf die nachfolgenden Knoten bestehen aus

• Der Zugriff auf die gesamte verknüpfte Liste muss beim Kopfzeiger beginnen, der auf den ersten Knoten

• dem letzten Knoten zeigt Der Zeiger zeigt auf null (NULL)

Mehrere Hauptoperationen in der verknüpften Liste

• Knoten erstellen

• Knoten einfügen

• Knoten suchen/durchqueren

• Knoten löschen

• Zusammenführen

Knoten initialisieren

• Zeiger zeigt auf Null

• Speicherdaten

    class Node {
        constructor(key) {
            this.next = null;
            this.key = key;
        }
    }

Einseitig verknüpfte Liste initialisieren

• Jede verknüpfte Liste hat einen Kopfzeiger, der auf den ersten Knoten zeigt. Wenn kein Knoten vorhanden ist, zeigt er auf NULL

    class List {
        constructor() {
            this.head = null;
        }
    }

Knoten erstellen

    static createNode(key) {
        return new createNode(key);
    }

Lassen Sie mich hier erklären, dass ich eine statische Methode zum Erstellen des Knotens verfügbar gemacht habe, anstatt ihn direkt in den Einfügevorgang einzukapseln, weil ich das Gefühl habe, dass eine solche Logik wird mehr sein. Seien Sie korrekter. Erstellen Sie eine verknüpfte Liste aus -> Erstellen Sie einen Knoten -> Fügen Sie den Knoten in die verknüpfte Liste ein. Möglicherweise stoßen Sie auf einige Artikel, die eine Möglichkeit vorstellen, ein Datenelement direkt als Parameter zum Aufrufen der Einfügeoperation zu verwenden und einen Knoten innerhalb der Einfügung zu erstellen.

Knoten einfügen (nach dem Einfügen in den Kopfknoten)

Der Einfügevorgang muss nur den Zeiger des Knotens anpassen. Es gibt zwei Fälle:

• Kopf existiert nicht. Zeigt auf einen Knoten, was darauf hinweist, dass der aktuell eingefügte Knoten der erste ist.

• Kopf zeigt auf den Knoten

• Kopf zeigt auf den neuen Knoten

• Der Zeiger des neuen Knotens zeigt auf den Knoten, auf den der ursprüngliche Kopf zeigt

•     insert(node) {
          // 如果head有指向的节点
          if(this.head){
             node.next = this.head;
          }else {
             node.next = null;
          }
          this.head = node;
      }

  Nach dem Knoten suchen

• Suche vom Kopf aus starten

Wenn festgestellt wird, dass der Schlüssel im Knoten gleich ist Geben Sie zum Schlüssel, den Sie finden möchten, den Knoten zurück

    find(key) {
        let node = this.head;
        while(node !== null && node.key !== key){
            node = node.next;
        }
        return node;
    }

Knoten löschen

Hier gibt es drei Teile Fall:

Der zu löschende Knoten ist zufällig der erste, nämlich der Knoten, auf den der Kopf zeigt.

Zeigen Sie mit dem Kopf auf den Knoten, den Sie löschen möchten. Löschen Sie den nächsten Knoten der Knoten (node.next)

• Der zu löschende Knoten ist der letzte Knoten

• Suchen Gehe zu vorheriger Knoten (prevNode)

• und zeigen Sie den Zeiger in prevNode auf NULL

• Löschen Sie etwas in der Mitte der Knotenliste

• Suchen Sie den vorherigen Knoten (prevNode) des zu löschenden Knotens

• Zeigen Sie den Zeiger in prevNode auf den aktuellen Knoten, der gelöscht werden soll gelöscht Der nächste Knoten dieses Knotens

•     delete(node) {
          // 第一种情况
          if(node === this.head){
              this.head = node.next;
              return;
          }
          
          // 查找所要删除节点的上一个节点
          let prevNode = this.head;
          while (prevNode.next !== node) {
              prevNode = prevNode.next;
          }
          
          // 第二种情况
          if(node.next === null) {
              prevNode.next = null;
          }
          
          // 第三种情况
          if(node.next) {
              prevNode.next = node.next;
          }
      }

  Der Gesamtcode der einseitig verknüpften Liste

  class ListNode {
    constructor(key) {
      this.next = null;
      this.key = key;
    }
  }
  
  class List {
    constructor() {
      this.head = null;
      this.length = 0;
    }
  
    static createNode(key) {
      return new ListNode(key);
    }
  
    // 往头部插入数据
    insert(node) {
      // 如果head后面有指向的节点
      if (this.head) {
        node.next = this.head;
      } else {
        node.next = null;
      }
      this.head = node;
      this.length++;
    }
  
    find(key) {
      let node = this.head;
      while (node !== null && node.key !== key) {
        node = node.next;
      }
      return node;
    }
  
    delete(node) {
      if (this.length === 0) {
        throw 'node is undefined';
      }
  
      if (node === this.head) {
        this.head = node.next;
        this.length--;
        return;
      }
  
      let prevNode = this.head;
  
      while (prevNode.next !== node) {
        prevNode = prevNode.next;
      }
  
      if (node.next === null) {
        prevNode.next = null;
      }
      if (node.next) {
        prevNode.next = node.next;
      }
      this.length--;
    }
  }

Doppelt verknüpfte Liste

• Wenn Sie haben die obige Einführung eingegeben. Wir haben die Einwegliste bereits verstanden, daher ist die hier eingeführte Zweiwegliste tatsächlich ähnlich.

Auf dem obigen Bild können Sie deutlich den Unterschied zwischen einer doppelt verknüpften Liste und einer einfach verknüpften Liste erkennen . Die doppelt verknüpfte Liste verfügt über einen zusätzlichen Zeiger, der auf den vorherigen Knoten zeigt.

Knoten initialisieren

Zeiger auf den vorherigen Knoten

指向后一个节点的指针

节点数据

    class ListNode {
        this.prev = null;
        this.next = null;
        this.key = key;
    }

初始化双向链表

• 头指针指向NULL

    class List {
        constructor(){
            this.head = null;
        }
    }

创建节点

    static createNode(key){
        return new ListNode(key);
    }

插入节点（（插入到头节点之后）

• 看上图中head后面的第一个节点可以知道，该节点的prev指向NULL

• 节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点

• 如果head后有节点，那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)

• 最后将head指向新的节点

    insert(node) {
        node.prev = null;
        node.next = this.head;
        if(this.head){
            this.head.prev = node;
        }
        this.head = node;
    }

搜索节点

这里和单向节点一样，就直接贴代码了

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

删除节点

和之前单向链表一样，分三种情况去看：

• 删除的是第一个节点

• head指向所要删除节点的下一个节点

• 下一个节点的prev指针指向所要删除节点的上一个节点

• 删除的是中间的某个节点

• 所要删除的前一个节点的next指向所要删除的下一个节点

• 所要删除的下一个节点的prev指向所要删除的前一个节点

• 删除的是最后一个节点

• 要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址）

    delete(node) {
        const {prev,next} = node;
        delete node.prev;
        delete node.next;
        if(node === this.head){
            this.head = next;
        }
        if(next){
            next.prev = prev;
        }
        if(prev){
            prev.next = next;
        }
    }

双向链表整体代码

    class ListNode {
  constructor(key) {
    // 指向前一个节点
    this.prev = null;
    // 指向后一个节点
    this.next = null;
    // 节点的数据(或者用于查找的键)
    this.key = key;
  }
}

/**
 * 双向链表
 */
class List {
  constructor() {
    this.head = null;
  }

  static createNode(key) {
    return new ListNode(key);
  }

  insert(node) {
    node.prev = null;
    node.next = this.head;
    if (this.head) {
      this.head.prev = node;
    }
    this.head = node;
  }

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

  delete(node) {
    const { prev, next } = node;
    delete node.prev;
    delete node.next;

    if (node === this.head) {
      this.head = next;
    }

    if (prev) {
      prev.next = next;
    }
    if (next) {
      next.prev = prev;
    }
  }
}

总结

这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in verknüpfte Listen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!