Comment implémenter une liste à lien unique en JavaScript

Bonjour ?, bienvenue dans cette série de listes chaînées. Dans notre dernier article, nous avons découvert les bases des listes chaînées, notamment leur définition, leurs terminologies, leurs différences avec les tableaux et les types de listes chaînées. J'ai promis que nous approfondirions la mise en œuvre des listes chaînées, alors commençons.

Plan du cours

1. Présentation
2. Implémentation de listes à lien unique
   • Création d'un nouveau nœud
   • Insérer au début
   • Insérer à la fin
   • Supprimer un nœud
   • Rechercher un nœud
   • Parcourir la liste
3. Conclusion

Introduction

Comme nous l'avons appris dans l'article précédent, les listes chaînées sont des structures de données fondamentales dans le monde de la programmation. Ils sont constitués de nœuds, où chaque nœud contient des données et une référence (ou un lien) vers le nœud suivant (dans une liste à chaînage unique) ou vers les nœuds suivant et précédent (dans une liste doublement chaînée) dans la séquence. Contrairement aux tableaux, les listes chaînées ne stockent pas d'éléments dans des emplacements mémoire contigus, ce qui permet des insertions et des suppressions efficaces.

Comprendre le concept de liste chaînée est crucial pour maîtriser les structures de données et les algorithmes. Dans cet article, nous approfondirons la mise en œuvre des listes chaînées, en commençant par les bases d'une liste chaînée unique.

Implémentation de listes à lien unique

Une liste chaînée unique est le type de liste chaînée le plus simple, où chaque nœud pointe vers le nœud suivant dans la séquence. Tout comme dans l'image ci-dessous.

Maintenant, il est temps de commencer à mettre en œuvre nos opérations de base sur les listes à chaînage unique. On y va ?

Création d'un nouveau nœud

Commençons par créer une nouvelle classe Node. La classe Node aura un constructeur qui récupère les données du nœud et un pointeur suivant initialement défini sur null.

// Node class for Singly Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Cette classe Node nouvellement créée (qui représente un nœud dans la liste chaînée) peut être visualisée comme ci-dessous.

Avant de continuer, créons une nouvelle instance de notre classe SinglyLinkedList qui contiendra nos opérations de liste chaînée.

// Singly Linked List class
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Operations come here ?
}

Insérer au début

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the beginning
  insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // Set the new node's next pointer to the current head
    this.head = newNode; // Update the head to be the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explication : Insérer au début, c'est comme si quelqu'un de nouveau rejoignait la file d'attente à l'avant. Ils deviennent la nouvelle première personne, établissant un lien avec la première précédente.

Insérer à la fin

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data); // Create a new node with the given data

    // check if the list does not have a head i.e the list is empty
    // NOTE: Every non-empty linked list will have a head
    if (!this.head) {
      this.head = newNode; // If the list is empty, set the new node as the head
      return;
    }
    let current = this.head; // Start at the head of the list
    while (current.next) {
      current = current.next; // Move to the next node in the list by updating the current node
    }
    current.next = newNode; // Set the next pointer of the last node to the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explication : Insérer à la fin, c'est comme si quelqu'un rejoignait la ligne à la toute fin. Nous devons marcher jusqu'au bout pour trouver la dernière personne, puis la relier à la nouvelle personne.

Supprimer un nœud

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

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return; // If the list is empty, do nothing
    if (this.head.data === data) {
      this.head = this.head.next; // If the node to delete is the head, update the head to the next node
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
        return;
      }
      current = current.next;
    }
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explication : Supprimer un nœud, c'est comme si quelqu'un au milieu de la file décidait de partir. Nous trouvons cette personne et connectons celle qui la précède à celle qui la suit.

Rechercher un nœud

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

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Search note
  search(data) {
    let current = this.head; // Start at the head of the list
    while (current) {
      if (current.data === data) {
        // If the data is found, return true
        return true;
      }
      current = current.next; // Move to the next node
    }
    return false;
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explication : Rechercher un nœud, c'est comme essayer de trouver une personne spécifique dans la ligne. Nous commençons par l'avant et interrogeons chaque personne jusqu'à ce que nous la trouvions ou arrivions à la fin.

Parcourez la liste

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  traverse() {
    let current = this.head; // Start at the head of the list
    while (current) {
      console.log(current.data); // Print the data of the current node
      current = current.next; // Move to the next node
    }
  }
}

// End of class

Explication : Traverser, c'est comme parcourir la ligne et saluer chaque personne. Nous commençons par l'avant et continuons d'avancer jusqu'à la fin.

Conclusion

Dans cet article, nous avons découvert les opérations de base des listes chaînées et comment les implémenter en JavaScript. Dans le prochain article, nous découvrirons les listes doublement liées.

N'oubliez pas que la maîtrise des listes chaînées nécessite de la pratique. Continuez à résoudre les problèmes et à mettre en œuvre ces structures de données dans divers scénarios.

Restez à jour et connecté

Pour vous assurer de ne manquer aucune partie de cette série et pour me contacter pour des discussions plus approfondies sur le développement de logiciels (Web, serveur, mobile ou Scraping/automatisation), les structures de données et les algorithmes, ainsi que d'autres technologies passionnantes. sujets, suivez-moi sur :

• GitHub
• Linkedin
• X (Twitter)

Restez à l'écoute et bon codage ?‍??

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!