Programme JavaScript pour rechercher des éléments dans une liste chaînée

Une liste chaînée est une structure de données linéaire dans laquelle chaque élément (également appelé nœud) contient une valeur de données et une référence au nœud suivant de la liste. Une opération courante sur une liste chaînée consiste à rechercher un élément spécifique. Cela implique de parcourir la liste et de comparer la valeur des données de chaque nœud à l'élément cible jusqu'à ce qu'une correspondance soit trouvée.

Voici un exemple de la liste de liens que nous utiliserons tout au long de cet article -

10 -> 20 -> 30 -> 40 -> Vide

Dans cette liste chaînée, chaque nœud contient une valeur et la flèche indique le nœud suivant dans la séquence. La liste commence par le nœud principal, qui contient la valeur 10, et se termine par le nœud final, qui contient la valeur 40 et pointe vers null. Nous utiliserons cette liste chaînée pour montrer comment rechercher un élément dans une liste chaînée à l'aide de JavaScript.

Voyons l'exemple ci-dessous -

Linked list: 10 -> 20 -> 30 -> 40 -> null
Input: 40
Output: Element found at index 3
Input: 10
Output: Element found at index 0
Input: null
Output: Element not found

Parlons maintenant de l'algorithme de création de listes chaînées en JavaScript.

Algorithme

Étape 1 - Définissez une classe Node avec deux propriétés : value et next. L'attribut value représente les données stockées dans le nœud et l'attribut suivant est une référence au nœud suivant dans la liste chaînée.

Étape 2 - Définissez une classe LinkedList avec trois propriétés : head, tail et length. L'attribut head représente le premier nœud de la liste chaînée, l'attribut tail représente le dernier nœud de la liste chaînée et l'attribut length représente le nombre de nœuds dans la liste chaînée.

Étape 3 - Définir une méthode nommée - ajouter à la classe LinkedList qui prend une valeur comme paramètre. La méthode add doit créer un nouveau nœud avec la valeur donnée et l'ajouter à la fin de la liste chaînée.

Étape 4 - Définissez une méthode appelée "remove" pour la classe LinkedList qui prend une valeur comme paramètre. La méthode Remove doit supprimer le premier nœud avec une valeur donnée dans la liste chaînée.

Étape 5 - Définissez une méthode appelée recherche pour la classe LinkedList qui prend une valeur comme paramètre. La méthode de recherche doit renvoyer le premier nœud de la liste chaînée avec la valeur donnée, ou null si le nœud n'est pas trouvé.

Étape 6 - Définissez une méthode appelée reverse pour la classe LinkedList, qui est utilisée pour inverser l'ordre des nœuds dans la liste chaînée.

Exemple : implémentez l'algorithme ci-dessus à l'aide de JavaScript

Le programme suivant définit une classe Node et une classe LinkedList. La classe Node crée un nouveau nœud en utilisant la valeur de données donnée et une référence au nœud suivant dans la liste. La classe LinkedList crée une nouvelle liste chaînée avec le nœud principal pointant initialement vers null et la propriété size définie sur 0. La méthode add ajoute un nouveau nœud à la fin de la liste chaînée. La méthode de recherche parcourt la liste chaînée et renvoie l'index de l'élément s'il est trouvé, ou un message s'il n'est pas trouvé. Enfin, le programme crée une nouvelle liste chaînée, y ajoute des éléments et recherche un élément spécifique.

// Define the Node class for a singly linked list
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
// Define the LinkedList class
class LinkedList {
   constructor() {
      this.head = null;
      this.size = 0;
   }
   // Add an element to the linked list
   add(element) {
      const node = new Node(element);
      // If the linked list is empty, set the new node as the head
      if (this.head === null) {
         this.head = node;
      } else {
         // Traverse to the end of the linked list and add the new node
         let current = this.head;
         while (current.next !== null) {
            current = current.next;
         }
         current.next = node;
      }
      this.size++;
   }
   // Search for an element in the linked list
   search(element) {
      let current = this.head;
      let index = 0;
      // Traverse through the linked list until the element is found
      while (current !== null) {
         if (current.data === element) {
            return `Element found at index ${index}`;
         }
         current = current.next;
         index++;
      }
      return "Element not found";
   }
}
// Create a new linked list
const ll = new LinkedList();
// Add elements to the linked list
ll.add(10);
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// Search for an element in the linked list
const result = ll.search(30);
console.log(result); 

Conclusion

La procédure de recherche d'éléments dans une liste chaînée à l'aide de JavaScript implique de créer une classe "LinkedList" qui définit des méthodes d'ajout d'éléments à la liste et de recherche d'éléments dans la liste. Le programme utilise une boucle while pour parcourir la liste chaînée et comparer l'élément de données de chaque nœud à l'élément qu'il recherche. Si l'élément est trouvé, le programme renvoie l'index du nœud, si l'élément n'est pas trouvé, le programme renvoie "Element not find".

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!