JavaScript implémente une liste doublement chaînée (exemple de code)

Dans cet article, nous allons vous présenter comment implémenter une liste doublement chaînée en JavaScript. Nous espérons que cela sera utile aux amis dans le besoin !

Qu'est-ce qu'une liste doublement chaînée

Dans une liste doublement chaînée, chaque nœud a une référence au nœud précédent et au nœud suivant. Les nœuds de début et de fin précédent et suivant doivent pointer vers null.

Implémentation d'une liste doublement chaînée

Nous utilisons la classe es6 Dans le code suivant, nous créons une classe auxiliaire Node. , qui contient trois données d'attributs, prev, next.

class Node {

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

data : les données que nous devons ajouter au nœud.

prev : fait référence au nœud précédent.

suivant : fait référence au nœud suivant.

L'algorithme principal commence

class DoublyLinkedList{

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

Dans le code ci-dessus, nous avons créé une classe DoublyLinkedList avec trois propriétés : head, tail et length.

head : C'est le premier nœud de la liste.

tail : Le dernier nœud de la liste.

longueur : Combien de nœuds y a-t-il dans la liste ?

Ajoutons ces fonctions à notre liste doublement chaînée

Méthode Push

La méthode Push nous aide à ajouter de nouveaux nœuds à la fin de la liste chaînée.

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. Dans le code ci-dessus, nous déclarons d'abord une nouvelle variable et appelons le constructeur de nœud.

2. S'il n'y a pas de this.head alors this.head et this.tail seront les nouveaux nœuds que nous avons créés à l'étape 1.

3. S'il existe déjà un nœud

le nouvel attribut node.prev devrait être this.tail

this.tail.next devrait être un nouveau nœud

Mettre à jour la queue.

4. Augmentez la longueur de 1. La

méthode pop

nous aide à supprimer le dernier nœud de la liste.

Dans une liste doublement chaînée, il est facile de supprimer le dernier nœud de la liste car il y a une référence au nœud précédent dans l'attribut tail.

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. Dans le code ci-dessus, nous déclarons d'abord une nouvelle variable et stockons l'attribut précédent de tail.

2. Si le nœud précédent est trouvé.

Supprimer le dernier nœud

Mettre à jour la queue.

3. Si le nœud précédent est vide, cela signifie qu'il n'y a qu'un seul nœud

this.head et this.tail doivent être nuls.

4. Réduisez la longueur de 1. La méthode

insertBeginning

insertBeginning nous aide à insérer un nouveau nœud au début de la liste.

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

  }

Méthode RemoveFirst

La méthode RemoveFirst nous aide à supprimer le premier nœud de la liste chaînée.

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

  }

Recommandations associées : "tutoriel javascript"

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!