Implémentation de LinkedList en Javascript

Une liste chaînée est une structure de données constituée d'une séquence d'éléments, chaque élément contenant une référence (ou "lien") vers l'élément suivant de la séquence. Le premier élément s’appelle la tête et le dernier élément s’appelle la queue.

La

Liste chaînée présente de nombreux avantages par rapport aux autres structures de données. Voyons maintenant comment implémenter une liste chaînée à l'aide de JavaScript.

Définissez la classe Node et la classe LinkedList

Il s'agit essentiellement d'une condition préalable à l'implémentation de listes chaînées en JavaScript. Dans cette étape, vous devez créer 2 classes, une pour les nœuds et une autre pour les listes chaînées.

La classe Node représente un seul nœud dans une liste chaînée. Il a deux propriétés : data et next. L'attribut data est utilisé pour stocker les données réelles du nœud, tandis que l'attribut suivant est une référence au nœud suivant dans la liste. La classe Node se compose d'un constructeur qui initialise les données et les propriétés suivantes lors de la création d'un nouveau Node.

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

La classe LinkedList est une représentation de la liste chaînée elle-même. Il possède un attribut head qui fait référence au premier nœud de la liste. La classe LinkedList possède également un constructeur qui initialise la propriété head lors de la création d'une nouvelle LinkedList.

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

La classe LinkedList contient également une méthode qui permet d'insérer, de supprimer et de rechercher des nœuds dans la liste, tout en permettant d'autres opérations comme l'impression de la liste, le comptage des éléments, l'inversion de la liste, etc.

Imprimer la liste des liens

Vous pouvez imprimer les éléments d'une liste chaînée en parcourant la liste chaînée et en imprimant les données de chaque nœud.

printAll() {
   let current = this.head;
   while (current) {
      console.log(current.data);
      current = current.next;
   }
}

Ajouter un nœud à la liste chaînée

Il existe plusieurs façons d'ajouter des données à une liste chaînée, selon l'endroit où le nouveau nœud doit être inséré, comme suit -

Ajouter un nœud au début de la liste chaînée

Pour ajouter un nœud/élément au début d'une liste chaînée, une fois que vous avez créé un nouveau nœud avec des données, définissez simplement sa propriété suivante sur l'en-tête actuel de la liste chaînée. Vous pouvez ensuite mettre à jour l'en-tête de la liste chaînée vers le nouveau nœud. Ceci est également appelé insertion de tête de liste chaînée et constitue le type d’ajout de données le plus basique. Cela se fait simplement en appelant la fonction add définie ci-dessous.

add(data) {
   const newNode = new Node(data);
   if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
   } else {
      this.tail.next = newNode;
      this.tail = newNode;
   }
   this.length++;
   return this;
}

Ajouter un nœud à la fin de la liste chaînée

Pour ajouter un nœud/élément à la fin de la liste chaînée, nous devons parcourir la liste chaînée et trouver le dernier nœud. Créez ensuite un nouveau nœud avec les données et définissez la propriété suivante du dernier nœud sur le nouveau nœud. Ceci est également appelé insertion de queue d’une liste chaînée et constitue le deuxième type d’ajout de données le plus basique. Cela se fait simplement en appelant la fonction addToTail définie ci-dessous.

addToTail(data) {
   let newNode = new Node(data);
   if (this.head === null) {
      this.head = newNode;
      return;
   }
   let current = this.head;
   while (current.next !== null) {
      current = current.next;
   }
   current.next = newNode;
}

Ajouter un nœud à un emplacement spécifique

Pour ajouter un nœud/élément à une position spécifique dans la liste chaînée, vous pouvez parcourir la liste chaînée pour trouver le nœud à la position avant le point d'insertion, créer un nouveau nœud avec les données, définir l'attribut suivant du nouveau nœud au nœud actuel à cette position et modifiez l'attribut du nœud précédent. L'attribut suivant est défini sur le nouveau nœud.

addAtPosition(data, position) {
   let newNode = new Node(data);
   if (position === 1) {
      newNode.next = this.head;
      this.head = newNode;
      return;
   }
   let current = this.head;
   let i = 1;
   while (i < position - 1 && current) {
      current = current.next;
      i++;
   }
   if (current) {
      newNode.next = current.next;
      current.next = newNode;
   }
}

Exemple (ajouter un nœud à la liste chaînée)

Dans l'exemple ci-dessous, nous avons ajouté des nœuds au début, à la fin et à des positions spécifiques.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   // function to add data to linked list
   add(data) {
      const newNode = new Node(data);
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } else {
         this.tail.next = newNode;
         this.tail = newNode;
      }
      this.length++;
      return this;
   }
   
   //function to add data to tail
   addToTail(data) {
      let newNode = new Node(data);
      if (this.head === null) {
         this.head = newNode;
         return;
      }
      let current = this.head;
      while (current.next !== null) {
         current = current.next;
      }
      current.next = newNode;
   }
   
   // function to insert data to linked list at a particular index
   addAtPosition(data, position) {
      let newNode = new Node(data);
      if (position === 1) {
         newNode.next = this.head;
         this.head = newNode;
         return;
      }
      let current = this.head;
      let i = 1;
      while (i < position - 1 && current) {
         current = current.next;
         i++;
      }
      if (current) {
         newNode.next = current.next;
         current.next = newNode;
      }
   }
   
   // this function is used to iterate over the entire linkedlist and print
   it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();

// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("List after adding nodex at position 2");
list.addAtPosition("nodex",2);
list.printAll();
console.log("List after adding nodey to tail");
list.addToTail("nodey");
list.printAll();

Sortie

Initial List:
node1
node2
node3
node4

List after adding nodex at position 2
node1
nodex
node2
node3
node4
List after adding nodey to tail
node1
nodex
node2
node3
node4
nodey

Supprimer le nœud

Les données peuvent également être supprimées via diverses méthodes sur demande.

Supprimer un nœud spécifique

Pour supprimer un nœud spécifique de la liste chaînée, nous devons parcourir la liste chaînée et trouver le nœud avant le nœud à supprimer, mettre à jour sa propriété suivante pour ignorer le nœud à supprimer et mettre à jour la référence au nœud suivant. Cela supprimera le nœud en fonction de la valeur.

remove(data) {
   if (!this.head) {
      return null;
   }
   if (this.head.data === data) {
      this.head = this.head.next;
      this.length--;
      return this;
   }
   let current = this.head;
   while (current.next) {
      if (current.next.data === data) {
         current.next = current.next.next;
         this.length--;
         return this;
      }
      current = current.next;
   }
   return null;
}

Supprimer des nœuds à des emplacements spécifiques

Pour supprimer un nœud à une position spécifique dans la liste chaînée, nous devons parcourir la liste chaînée et trouver le nœud avant le nœud à supprimer, mettre à jour sa propriété suivante pour ignorer le nœud à supprimer, puis mettre à jour la référence à le nœud suivant. Cela supprime essentiellement les nœuds en fonction de leur valeur d'index.

removeAt(index) {
   if (index < 0 || index >= this.length) return null;
   if (index === 0) return this.remove();
   let current = this.head;
   for (let i = 0; i < index - 1; i++) {
      current = current.next;
   }
   current.next = current.next.next;
   this.length--;
   return this;
}

Exemple (suppression de nœuds de la liste linéaire)

Dans l'exemple ci-dessous, nous implémentons la suppression de nœuds spécifiques et de nœuds à des emplacements spécifiques.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   // function to add data to linked list
   add(data) {
      const newNode = new Node(data);
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } 
      else {
         this.tail.next = newNode;
         this.tail = newNode;
      }
      this.length++;
      return this;
   }
   
   // function to remove data from linked list
   remove(data) {
      if (!this.head) {
         return null;
      }
      if (this.head.data === data) {
         this.head = this.head.next;
         this.length--;
         return this;
      }
      let current = this.head;
      while (current.next) {
         if (current.next.data === data) {
            current.next = current.next.next;
            this.length--;
            return this;
         }
         current = current.next;
      }
      return null;
   }
   
   // function to remove from a particular index 
      removeAt(index) {
      if (index < 0 || index >= this.length) return null;
      if (index === 0) return this.remove();
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
         current = current.next;
      }
      current.next = current.next.next;
      this.length--;
      return this;
   }
   
   // this function is used to iterate over the entire linkedlist and print it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();
// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("List after removing node2");
list.remove("node2");
list.printAll();
console.log("List after removing node at index 2");
list.removeAt(2);
list.printAll();

Sortie

Initial List:
node1
node2
node3
node4
List after removing node2
node1
node3
node4

List after removing node at index 2
node1
node3

Conclusion

L'implémentation d'une liste chaînée en JavaScript implique de créer une classe Node pour représenter chaque nœud de la liste et une classe LinkedList pour représenter la liste elle-même, et d'ajouter des méthodes à la classe LinkedList pour effectuer des opérations telles que l'ajout et la suppression de données et l'impression de la liste. Il est important de prendre également en compte les cas extrêmes et de les gérer en conséquence lors de la mise en œuvre. Selon le cas d'utilisation, il existe plusieurs façons d'ajouter ou de supprimer des données d'une LinkedList.

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!