Introduction détaillée aux listes chaînées en JavaScript-js tutoriel-php.cn

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>Liste chaînée unidirectionnelle</h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" title="1546394138978971.png" alt="Introduction détaillée aux listes chaînées en JavaScript"></span></p><h4>Caractéristiques de la liste chaînée unidirectionnelle : </h4>

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

Créer un nœud

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

Copier après la connexion

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

Rechercher le nœud
Lancer la recherche depuis la tête

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

Copier après la connexion

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

Copier après la connexion

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

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

Le code de la liste chaînée unidirectionnelle globale
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;
        }
    }

Copier après la connexion

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

Copier après la connexion

À 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

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

Pointeur vers le nœud précédent

指向后一个节点的指针

节点数据

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

Copier après la connexion

初始化双向链表

头指针指向NULL

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

Copier après la connexion

创建节点

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

Copier après la connexion

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

看上图中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;
    }

Copier après la connexion

搜索节点

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

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

Copier après la connexion

删除节点

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

删除的是第一个节点

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

删除的是中间的某个节点

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

删除的是最后一个节点

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

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

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

Copier après la connexion

双向链表整体代码

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

Copier après la connexion