Pouvez-vous expliquer ce qu'est une liste chaînée et comment elle fonctionne?

Une liste chaînée est une structure de données composée de nœuds, où chaque nœud contient des données et une référence au nœud suivant dans la liste. Contrairement aux tableaux, les listes chaînées ne nécessitent pas un bloc de mémoire contigu et permettent d’insérer et de supprimer des éléments efficacement.

Principaux types de listes chaînées :

• Liste simplement chaînée : chaque nœud ne contient qu’une référence au nœud suivant.
• Liste doublement chaînée : chaque nœud contient des références au nœud suivant et au nœud précédent.

Exemple de liste simplement chaînée en JavaScript (Node.js) :

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

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

  add(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
}

Les listes chaînées sont utiles lorsque la structure doit changer de taille dynamiquement et que des insertions/suppressions fréquentes sont nécessaires.