Supprimer un nœud dans une liste chaînée en C++

Jinku Hu 12 octobre 2023

C++ C++ Data Structure

Supprimer un nœud dans une liste chaînée en C++

Cet article explique comment implémenter une fonction qui supprime un nœud donné dans une liste chaînée C++.

Implémenter une fonction pour supprimer un nœud donné dans une liste chaînée

Dans cet article, nous implémentons une liste à chaînage unique à partir de zéro sans utiliser les conteneurs de STL. Ainsi, nous devons définir certaines fonctions nécessaires pour gérer les nœuds dans une liste chaînée.

L’élément insertNode est la fonction principale qui doit être invoquée pour créer une nouvelle liste chaînée. Puisque nous devons stocker la tête de la liste, le insertNode renvoie le pointeur vers le nœud de type ListNode. Ce dernier est la représentation minimale du nœud de liste chaînée. Il ne contient qu’un pointeur vers le nœud suivant et l’objet de données string.

Pendant le test et la démonstration du programme, il est important d’avoir des fonctions utilitaires pour afficher certains messages sur la console utilisateur. Dans ce cas, l’élément printNodes est utilisé pour imprimer tous les nœuds de la structure de liste donnée. De plus, nous devons désallouer chaque nœud existant dans la liste à la sortie du programme en utilisant la fonction freeNodes lors de l’allocation de nouveaux nœuds sur la mémoire dynamique.

Une fois que nous avons construit une liste avec les données arbitraires, comme indiqué dans la fonction main de l’extrait de code suivant, nous sommes prêts à invoquer deleteNode, qui implémente l’opération de suppression de nœud. La suppression d’un nœud nécessite que plusieurs cas d’angle soient traités dans celui-ci. A savoir, le scénario lorsque le nœud donné est le même que la tête de la liste et l’autre lorsque le nœud donné est le seul nœud de la liste.

Dans ce dernier scénario, nous pouvons simplement appeler l’opérateur delete sur le pointeur de nœud et revenir de la fonction. Bien qu’il soit important d’affecter nullptr à l’adresse car cela nous aidera à ajouter de nouveaux éléments à la même variable head dans la fonction principale.

D’un autre côté, supprimer le nœud principal lorsqu’il y a d’autres nœuds dans la liste est relativement délicat. Nous devons copier le contenu du deuxième nœud dans le nœud principal et supprimer le premier. Notez que chaque cas renvoie la valeur EXIT_SUCCESS pour indiquer un appel de fonction réussi.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNode(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

int deleteNode(struct ListNode *root, struct ListNode *node) {
  if (node == nullptr || root == nullptr) return EXIT_FAILURE;

  if (root == node) {
    if (root->next == nullptr) {
      delete node;
      root = nullptr;
      return EXIT_SUCCESS;
    }

    node = root->next;
    root->data = root->next->data;
    root->next = root->next->next;
    delete node;
    return EXIT_SUCCESS;
  }

  auto prev = root;
  while (prev->next != node && prev->next != nullptr) {
    prev = prev->next;
  }

  prev->next = node->next;
  delete node;
  return EXIT_SUCCESS;
}

void freeNodes(struct ListNode *root) {
  struct ListNode *tmp = nullptr;
  while (root) {
    tmp = root;
    root = root->next;
    delete tmp;
  }
}

void printNodes(struct ListNode *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct ListNode *head = nullptr;

  head = insertNode(head, "Xenial");

  insertNode(head, "Artful");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  deleteNode(head, head);
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Production:

node 0 - data : Xenial node 1 -
                data
    : Artful-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Artful

Le code de fonction restant implémente le cas normal, où le nœud donné est décroché de la chaîne de liste puis désalloué à l’aide de l’opérateur delete. Notez, cependant, que cette opération nécessite que le nœud précédent soit trouvé, qui est l’opération temporelle linéaire pour chaque nœud sauf à partir de la tête de la liste. Habituellement, il faut stocker la fin de la liste dans la structure de la liste chaînée afin de garantir la suppression à temps constant pour la fin de la liste.

L’extrait de code suivant illustre un scénario de fonction main différent, dans lequel un nœud est supprimé du milieu de la liste.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNode(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

int deleteNode(struct ListNode *root, struct ListNode *node) {
  if (node == nullptr || root == nullptr) return EXIT_FAILURE;

  if (root == node) {
    if (root->next == nullptr) {
      delete node;
      root = nullptr;
      return EXIT_SUCCESS;
    }

    node = root->next;
    root->data = root->next->data;
    root->next = root->next->next;
    delete node;
    return EXIT_SUCCESS;
  }

  auto prev = root;
  while (prev->next != node && prev->next != nullptr) {
    prev = prev->next;
  }

  prev->next = node->next;
  delete node;
  return EXIT_SUCCESS;
}

void freeNodes(struct ListNode *root) {
  struct ListNode *tmp = nullptr;
  while (root) {
    tmp = root;
    root = root->next;
    delete tmp;
  }
}

void printNodes(struct ListNode *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct ListNode *head = nullptr;

  head = insertNode(head, "Xenial");

  auto iter = insertNode(head, "Bionic");
  insertNode(head, "Artful");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  deleteNode(head, iter);
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Production:

node 0 - data : Xenial node 1 - data : Bionic node 2 -
                                       data
    : Artful-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Xenial node 1 - data : Artful

Auteur: Jinku Hu

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Implémenter une fonction pour supprimer un nœud donné dans une liste chaînée

Article connexe - C++ Data Structure