Introduction détaillée aux listes chaînées en JavaScript

Cet article vous apporte une introduction détaillée aux listes chaînées en JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Listes et tableaux chaînés

Tout le monde a utilisé des tableaux en js. Les tableaux sont en fait une structure de stockage séquentielle de tables linéaires. Sa caractéristique est qu'il utilise un ensemble d'adresses. . Les cellules mémoire consécutives stockent les éléments de données les uns après les autres. Ses inconvénients sont également dus à ses caractéristiques. Par exemple, lors de la suppression ou de l'insertion d'un tableau, un grand nombre d'éléments peuvent devoir être déplacés.

Voici une simulation approximative de l'opération d'insertion du tableau :

    insert(arr, index, data){
        for(let i = index + 1; i <p>À partir du code ci-dessus, nous pouvons voir que l'insertion et la suppression du tableau peuvent être un O(n ) opération. Cela conduit à la structure de données de la liste chaînée. La liste chaînée ne nécessite pas que les éléments logiquement adjacents soient adjacents dans des emplacements physiques, elle n'a donc pas les inconvénients de la structure de stockage séquentielle. Bien sûr, elle perd également le caractère aléatoire de la liste chaînée. tableau dans un espace continu. Avantages de l'accès. </p><h3 id="Liste-chaînée-unidirectionnelle">Liste chaînée unidirectionnelle</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="Introduction détaillée aux listes chaînées en JavaScript"></span></p><h4 id="Caractéristiques-de-la-liste-chaînée-unidirectionnelle">Caractéristiques de la liste chaînée unidirectionnelle : </h4>

• Utilisez-en un Organisez n'importe quel espace mémoire pour stocker des éléments de données (l'espace mémoire ici peut être continu ou discontinu)

• Chaque nœud (nœud) se compose des données elles-mêmes et d'un pointeur vers les suivants les nœuds sont composés de

• L'accès à l'intégralité de la liste chaînée doit commencer à partir du pointeur de tête, qui pointe vers le premier nœud

• le dernier nœud Le pointeur pointe vers null (NULL)

Plusieurs opérations principales dans la liste chaînée

• Créer un nœud

• Insérer un nœud

• Rechercher/Nœud de parcours

• Supprimer un nœud

• Fusionner

Initialiser le nœud

• Le pointeur pointe vers null

• Données de stockage

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

Initialiser la liste chaînée unidirectionnelle

• Chaque liste chaînée a un pointeur de tête, pointant vers le premier nœud, s'il n'y a pas de nœud, il pointe vers NULL

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

Créer un nœud

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

Laissez-moi vous expliquer ici, j'ai exposé une méthode statique pour créer le nœud, au lieu de l'encapsuler directement dans l'opération d'insertion, parce que j'ai l'impression que cette logique serait plus correcte. Créez une liste chaînée à partir de -> Créer un nœud -> Insérez le nœud dans la liste chaînée. Vous pouvez rencontrer des articles qui présentent un moyen d'utiliser directement un élément de données comme paramètre pour appeler l'opération d'insertion et de créer un nœud à l'intérieur de l'insertion.

Insérer un nœud (après insertion dans le nœud principal)

L'opération d'insertion nécessite uniquement d'ajuster le pointeur du nœud :

• <.>head n'existe pas Pointe vers un nœud, indiquant que le nœud actuellement inséré est le premier

• head pointe vers le nœud

• la tête pointe vers le nouveau nœud

Le pointeur du nouveau nœud pointe vers le nœud pointé par la tête d'origine
• Rechercher le nœud

• Lancer la recherche depuis la tête

Lorsque la clé dans le nœud est trouvée pour être égal à la clé que vous souhaitez trouver, renvoyer le nœud

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

Supprimer le nœud

• Il y a trois situations ici :

• Le nœud à supprimer se trouve être le premier, qui est le nœud pointé par head

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

Pointez head vers le nœud suivant (node.next) du nœud à supprimer

• Le nœud à supprimer est le dernier nœud

• Rechercher le nœud précédent ( prevNode) du nœud à supprimer

Pointez le pointeur dans prevNode sur NULL
Supprimez un nœud au milieu du list
• Trouver le nœud précédent (prevNode) du nœud à supprimer

Changer le pointeur dans prevNode Points vers le suivant nœud du nœud actuellement à supprimer
• Le code de la liste chaînée unidirectionnelle globale

Liste double chaînée

• Si vous comprenez la liste à sens unique présentée ci-dessus, alors la liste à double sens présentée ici est en fait presque la même.

    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;
        }
    }

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--;
  }
}

À partir de l'image ci-dessus, vous pouvez clairement voir la différence entre une liste doublement chaînée et une liste simplement chaînée . La liste doublement chaînée comporte un pointeur supplémentaire pointant vers le nœud précédent.

Initialiser le nœud

Pointeur vers le nœud précédent

指向后一个节点的指针

节点数据

    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)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!