Implémenter une liste doublement chaînée en C++

1. Utilisez struct pour implémenter une liste doublement liée en C++
2. Utiliser le conteneur std::list comme liste doublement chaînée en C++

Cet article présentera plusieurs méthodes sur la façon d’implémenter une liste doublement chaînée en C++.

Utilisez struct pour implémenter une liste doublement liée en C++

Les listes chaînées sont considérées comme l’une des structures de données les plus courantes que vous pouvez rencontrer en programmation. Ces structures sont liées en ce sens que chaque nœud contient l’adresse d’un autre. Les listes chaînées ont deux types : les listes à chaînage simple et les listes à chaînage double. Une liste à liaison simple contient des nœuds qui pointent uniquement vers le nœud suivant de la liste ; ainsi, il rend la traversée de la structure unidirectionnelle. D’autre part, les listes doublement chaînées fournissent un accès bidirectionnel à partir de chaque nœud de la liste.

Dans ce cas, nous implémentons une liste doublement chaînée à l’aide de la commande struct, rendant toutes ses données membres publiques et définissant séparément les fonctions de manipulation des éléments. Notez que l’on peut préférer une version orientée objet avec des fonctions membres fournissant les routines de manipulation d’éléments et quelques membres de données d’enregistrement.

L’exemple de code suivant inclut le code du pilote dans la fonction main qui teste le scénario d’utilisation de base, où les éléments vectoriels string sont insérés dans une liste, puis la liste est désallouée. Nous utilisons l’opérateur new pour allouer dynamiquement chaque nœud, et par conséquent, la fonction freeNodes parcourt la liste pour appeler delete sur chaque Node.

La méthode d’allocation séparée de chaque Node pourrait être inefficace si l’utilisateur souhaite concevoir une structure de liste chaînée relativement performante. On pourrait envisager une allocation en masse de ressources mémoire pour ajouter rapidement de nouveaux nœuds et, lorsqu’elle n’est pas nécessaire, en désallouer plusieurs en même temps. Dans cette conception, nous commençons à construire la liste avec l’élément valide représentant le premier nœud de la structure. Certaines implémentations peuvent créer un élément factice, qui désigne la tête de la liste mais ne contient pas les données de l’élément.

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

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

struct Node {
  struct Node *next{};
  struct Node *prev{};
  string data;
};

template <typename T>
struct Node *addNewNode(struct Node *node, T &data) {
  auto new_node = new Node;
  if (node) node->next = new_node;
  new_node->prev = node;
  new_node->next = nullptr;
  new_node->data = data;
  return new_node;
}

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

void printNodeData(struct Node *node) {
  cout << "data: " << node->data << endl;
}

int main() {
  struct Node *tmp, *root = nullptr;
  struct Node *end = nullptr;

  vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
                             "Meteor Lake"};

  root = addNewNode(root, data_set.at(0));
  tmp = root;
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    tmp = addNewNode(tmp, *it);
    if (it == data_set.end() - 1) end = tmp;
  }

  printNodeData(root);
  printNodeData(end);

  freeNodes(root);
  return EXIT_SUCCESS;
}

Production:

data : Rocket Lake data : Meteor Lake

Vous pouvez utiliser des listes chaînées comme blocs de construction de structures de données plus spécialisées telles que des piles, des demandes, des files d’attente ou des listes circulaires. Ce dernier est intéressant car il s’agit essentiellement d’une liste doublement chaînée où le dernier nœud pointe vers le premier élément en tant que nœud suivant, et en conséquence le premier pointe vers le dernier élément en tant que nœud précédent. Notez que l’extrait de code suivant ajoute la fonction printNodes pour afficher le contenu de chaque nœud dans la liste construite.

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

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

struct Node {
  struct Node *next{};
  struct Node *prev{};
  string data;
};

struct Node *addNewNode(struct Node *node, string &data) {
  auto new_node = new Node;
  if (node) node->next = new_node;
  new_node->prev = node;
  new_node->next = nullptr;
  new_node->data = data;
  return new_node;
}

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

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

int main() {
  struct Node *tmp, *root = nullptr;
  struct Node *end = nullptr;

  vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
                             "Meteor Lake"};

  root = addNewNode(root, data_set.at(0));
  tmp = root;
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    tmp = addNewNode(tmp, *it);
    if (it == data_set.end() - 1) end = tmp;
  }

  printNodes(root);

  freeNodes(root);
  return EXIT_SUCCESS;
}

Production:

node 0 - data : Rocket Lake node 1 - data : Alder Lake node 2 -
                                            data : Tiger Lake node 3 -
                                                   data : Meteor Lake

Utiliser le conteneur std::list comme liste doublement chaînée en C++

Alternativement, on peut utiliser le conteneur std::list de C++ STL, qui est généralement implémenté sous forme de liste doublement chaînée et fournit diverses fonctions de manipulation d’éléments. De plus, le conteneur std::list est implémenté pour prendre en charge des algorithmes assez puissants inclus dans la bibliothèque standard afin que l’utilisateur puisse gagner du temps sur le développement si certaines caractéristiques de performances très spéciales ne sont pas requises.

#include <iostream>
#include <list>
#include <string>

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

template <typename T>
void printList(std::list<T> l) {
  for (const auto &item : l) {
    cout << item << "; ";
  }
  cout << endl;
}

int main() {
  std::list<int> l = {1, 2, 3, 4};
  l.push_back(5);
  l.push_front(0);
  printList(l);

  auto it = std::find(l.begin(), l.end(), 3);
  if (it != l.end()) {
    l.insert(it, 99);
  }
  printList(l);

  return EXIT_SUCCESS;
}

Production:

0;
1;
2;
3;
4;
5;
0;
1;
2;
99;
3;
4;
5;