Implémenter une structure de données de liste chaînée circulaire en C++

1. Implémenter une liste circulaire à chaînage simple avec des fonctions membres pour ajouter de nouveaux éléments à la fin et pour imprimer des éléments en C++
2. Implémenter le destructeur et la fonction membre pour insérer de nouveaux éléments au début de la liste en C++

Cet article explique comment implémenter une structure de données de liste chaînée circulaire en C++.

Implémenter une liste circulaire à chaînage simple avec des fonctions membres pour ajouter de nouveaux éléments à la fin et pour imprimer des éléments en C++

Une liste chaînée circulaire peut être caractérisée comme une liste chaînée où le dernier nœud pointe vers la tête de la liste. Essentiellement, les nœuds de la liste forment un cercle, et il n’y a pas de nullptr pour délimiter la fin de la liste. Vous pouvez utiliser des listes chaînées circulaires pour créer des structures de données de type file d’attente. La fonction de circularité peut être ajoutée à la fois à la liste à double chaînage et à une liste à chaînage simple.

Dans ce cas, nous allons implémenter ce dernier. N’oubliez pas que nous devons définir une structure de nœud qui inclut un pointeur vers le nœud suivant et un élément de données pour construire une liste à chaînage unique. L’objet struct ListNode représente un nœud unique pour notre implémentation et stocke un seul objet string nommé data, qui servira d’élément de données pour cet exemple. Notez que l’on peut stocker n’importe quel objet personnalisé dans un nœud, et si l’objet est relativement plus grand, il est préférable de l’inclure en tant que pointeur.

Une fois que nous avons une structure d’un seul nœud, nous pouvons définir une classe CircularList, qui n’a que deux fonctions membres pour commencer. En règle générale, une liste chaînée circulaire doit garder une trace de la tête de la liste ou de sa fin ; cependant, l’implémenteur est généralement libre de prendre la décision de conception de classe en fonction de ses besoins. De plus, la classe CircularList stocke deux pointeurs distincts pour représenter la tête et la fin de la liste.

Le pointeur qui stocke la tête/la fin de la liste peut être un nœud factice ou un nœud réel avec les données. Dans cet exemple, nous avons choisi de concevoir la classe CircularList pour qu’elle n’ait pas de pointeurs factices. Nous avons défini un constructeur pour accepter un paramètre string pour initialiser le premier nœud de la liste circulaire. Notez que les choix de conception lors de la définition de la classe affectent généralement différentes variables, qui doivent être prises en compte en fonction du problème sous-jacent. Ainsi, la mise en œuvre suivante est uniquement censée être simple pour expliquer le concept de listes chaînées circulaires.

Une fois l’objet CircularList initialisé à l’aide du constructeur, nous pouvons ajouter de nouveaux éléments à l’aide de la fonction membre insertNodeEnd. Ce dernier accepte le paramètre string et construit un nouvel élément à la fin de la liste. La fonction insertNodeEnd alloue de nouveaux éléments avec l’opérateur new et modifie les pointeurs en conséquence pour insérer le nœud juste après la fin de la liste. Il met également à jour le membre de données end pour pointer vers un nœud nouvellement alloué.

Une autre fonction membre définie dans l’exemple suivant est le printNodes, qui parcourt la liste pour imprimer son contenu et ne prend aucun argument. Maintenant, pour mieux démontrer l’utilisation de cette structure, nous avons besoin de code de pilote dans la fonction main. Nous avons choisi d’initialiser un vector de chaînes arbitraires plus tard à insérer dans l’objet CircularList à l’aide de la boucle for. Enfin, nous invoquons une fonction printNodes pour afficher le contenu de la liste au terminal.

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

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

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  void printNodes();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  end = end->next;
  return new_node;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  CircularList clist("Xenial");

  for (const auto &item : data_set) {
    clist.insertNodeEnd(item);
  }

  clist.printNodes();

  return EXIT_SUCCESS;
}

Production:

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

Implémenter le destructeur et la fonction membre pour insérer de nouveaux éléments au début de la liste en C++

Notez que l’extrait de code précédent a un énorme problème de ne pas avoir de destructeur défini ; cela implique que le programme utilisant la classe CircularList perdra de la mémoire puisque les nœuds créés sur la mémoire dynamique ne sont libérés qu’à la sortie du programme.

La solution à ce problème est d’implémenter un destructeur qui va parcourir toute la liste et désallouer tous les nœuds à l’aide de l’opérateur delete. Ainsi, nous n’avons pas à nous soucier de libérer manuellement la mémoire de la liste. Il sera automatiquement libéré une fois que l’objet CircularList atteindra la fin de portée.

Une autre fonction utile à implémenter est celle qui insère un nouvel élément en tête de liste ; la commande insertNodeHead est conçue pour faire exactement cela. Il ne prend qu’un argument string à stocker et renvoie le pointeur vers le nœud nouvellement alloué. Notez que la valeur de retour pour les fonctions insertNodeEnd et insertNodeHead est un autre choix de conception, qui est implémenté différemment selon les décisions du programmeur. L’extrait de code suivant inclut le code de pilote similaire dans la fonction main pour tester et présenter l’utilisation de la classe CircularList.

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

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

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  ListNode *insertNodeHead(string data);
  void printNodes();

  ~CircularList();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  end = end->next;
  return new_node;
}

ListNode *CircularList::insertNodeHead(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  head = end->next;
  return new_node;
}

CircularList::~CircularList() {
  while (head != end) {
    auto tmp = head;
    head = head->next;
    delete tmp;
  }
  delete head;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  CircularList clist("Xenial");

  for (const auto &item : data_set) {
    clist.insertNodeEnd(item);
  }

  clist.printNodes();
  cout << " ----------------------------------- " << endl;

  clist.insertNodeHead("Bionic");
  clist.insertNodeEnd("Zeisty");
  clist.printNodes();

  return EXIT_SUCCESS;
}

Production:

node 0 - data : Xenial node 1 - data : Precise node 2 - data : Quantal node 3 -
                                                               data
    : Saucy node 4 -
      data
    : Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Bionic node 1 - data : Xenial node 2 - data : Precise node 3 -
                                                           data
    : Quantal node 4 -
      data : Saucy node 5 - data : Raring node 6 - data : Zeisty