Insérer un nœud dans une liste à liens simples C++

  2. HowTo
  3. C++ Howtos
  4. Insérer un nœud dans une liste à liens …
Jinku Hu 12 octobre 2023
C++ C++ Data Structure
  1. Implémenter une fonction pour insérer un nœud à la fin d’une liste chaînée
  2. Implémenter une fonction pour insérer un nœud après un nœud donné dans une liste chaînée
  3. Implémenter une fonction pour insérer un nœud au début d’une liste chaînée
Insérer un nœud dans une liste à liens simples C++

Cet article explique la méthode d’insertion d’un nouveau nœud dans une liste à chaînage simple en C++.

Implémenter une fonction pour insérer un nœud à la fin d’une liste chaînée

Les listes chaînées sont des structures de données linéaires constituées de nœuds pointant les uns vers les autres, de manière séquentielle. Dans cet article, nous nous concentrons davantage sur une structure de liste chaînée unique et implémentons plusieurs opérations d’insertion en conséquence.

Dans une liste à chaînage simple, nous avons un ou plusieurs objets de données et un pointeur vers le nœud suivant de la liste. Nous avons défini une structure de nœuds nommée ListNode et deux fonctions d’aide (freeNodes et printNodes) pour mieux démontrer les opérations d’insertion de liste. Notez que la complexité du temps de l’opération d’insertion varie en fonction de la position dans laquelle nous insérons un nœud. Par exemple, l’insertion en fin de liste prend un temps linéaire si la fin de la liste est inconnue.

En revanche, l’insertion d’un nouveau nœud au début prend toujours un temps constant. Le code suivant illustre la fonction insertNodeEnd, qui peut être traitée comme la fonction principale pour construire une liste. Il prend la tête de la liste comme premier paramètre et les données string qui doivent être stockées sur un nouveau nœud. La fonction peut créer le premier élément de la liste et ajouter de nouveaux éléments à la fin. La fonction alloue de nouveaux nœuds sur la mémoire de stockage libre. Ainsi, la fonction freeNodes est nécessaire pour libérer toute la mémoire avant la sortie du programme.

#include <iostream>
#include <string>
#include <utility>
#include <vector>

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

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

struct ListNode *insertNodeEnd(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;
}

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;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeEnd(head, "Utopic");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Production:

node 0 - data : Precise node 1 - data : Quantal node 2 - data : Saucy node 3 -
                                                                data
    : Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Precise node 1 - data : Quantal node 2 -
                                     data : Saucy node 3 -
                                            data : Raring node 4 - data : Utopic

Implémenter une fonction pour insérer un nœud après un nœud donné dans une liste chaînée

L’insertion d’un nœud au milieu de la liste prend généralement un temps constant auquel s’ajoute la complexité temporelle de l’algorithme de recherche utilisé pour trouver la position donnée. Cependant, nous supposons que la fonction de recherche est implémentée séparément et construisons la fonction insertNodeAfter de sorte que la position du nœud cible doit être fournie comme premier argument.

Puisque la fonction insertNodeEnd renvoie le pointeur vers un nœud nouvellement ajouté, nous utilisons sa valeur de retour pour démontrer le fonctionnement de insertNodeAfter. Gardez à l’esprit que vous auriez besoin d’une fonction de recherche distincte pour les insertions de positions arbitraires et que vous pourriez même avoir besoin d’une structure de données externe pour implémenter une opération de recherche plus rapide sur une liste chaînée.

#include <iostream>
#include <string>
#include <utility>
#include <vector>

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

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

struct ListNode *insertNodeEnd(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;
}

struct ListNode *insertNodeAfter(struct ListNode *prev, string data) {
  if (!prev) return nullptr;

  auto new_node = new ListNode;
  new_node->next = nullptr;
  new_node->data = std::move(data);
  prev->next = new_node;
  return new_node;
}

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;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  auto iter = insertNodeEnd(head, "Utopic");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeAfter(iter, "Xenial");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Production:

node 0 - data : Precise node 1 - data : Quantal node 2 - data : Saucy node 3 -
                                                                data
    : Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Precise node 1 - data : Quantal node 2 - data : Saucy node 3 -
                                                             data
    : Raring node 4 -
      data : Utopic-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
             data : Precise node 1 - data : Quantal node 2 -
                                            data
    : Saucy node 3 -
      data : Raring node 4 - data : Utopic node 5 - data : Xenial

Implémenter une fonction pour insérer un nœud au début d’une liste chaînée

Une autre opération d’insertion utile pour la liste chaînée simple consiste à ajouter un nouveau nœud au début. Cette fonction a le meilleur temps d’exécution O(1) puisque la tête de liste est toujours stockée pour accéder à la liste elle-même. La fonction insertNodeFront prend la référence à un pointeur racine et à l’objet string qui doit être stocké au niveau du nœud. Le processus est implémenté afin que vous puissiez l’utiliser pour initialiser une nouvelle liste chaînée ainsi que l’insertion frontale.

Alternativement, vous pouvez réécrire la fonction pour allouer un nouveau nœud lorsque l’argument root n’est pas nullptr. Sinon, retourne nullptr pour indiquer que la fonction a échoué. L’interface de ces fonctions dépend des besoins des programmeurs et de la structure du ListNode.

#include <iostream>
#include <string>
#include <utility>
#include <vector>

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

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

struct ListNode *insertNodeEnd(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;
}

struct ListNode *insertNodeFront(struct ListNode *&root, string data) {
  auto new_node = new ListNode;
  if (root) {
    new_node->next = root;
    new_node->data = std::move(data);
    root = new_node;
    return root;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

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;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeFront(head, "Bionic");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Production:

node 0 - data : Precise node 1 - data : Quantal node 2 - data : Saucy node 3 -
                                                                data
    : Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Bionic node 1 - data : Precise node 2 -
                                    data : Quantal node 3 -
                                           data : Saucy node 4 - data : Raring
Auteur: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

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

Article connexe - C++ Data Structure