Liste circulaire doublement chaînée en C++

Jinku Hu 12 octobre 2023

C++ C++ Data Structure

Liste circulaire doublement chaînée en C++

Cet article montrera comment implémenter une liste doublement chaînée circulaire en C++.

Structure de données de liste doublement liée circulaire à partir de zéro en C++

Une liste doublement chaînée est une structure de données dans laquelle chaque nœud stocke des pointeurs vers les nœuds suivants et précédents. Cela en fait un choix optimal pour implémenter des conteneurs de type std::deque. Il serait préférable de faire une liste doublement chaînée circulaire pour que le membre next du dernier nœud pointe vers le début de la liste et que le premier nœud pointe également vers le dernier nœud comme son précédent.

Dans un premier temps, nous devons déclarer une struct nommée ListNode utilisée pour construire une liste. Ensuite, nous définissons une classe CircularList avec deux données membres de type ListNode* et des fonctions à trois membres.

Notez que nous avons décidé d’inclure un seul constructeur qui accepte une valeur string et initialise le premier nœud, mais cette partie peut être modifiée au gré du programmeur. Deux membres de données - head et end - stockent les premier et dernier nœuds. Nous avons également des fonctions distinctes pour ajouter des éléments de chaque côté de la liste.

#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;
  struct ListNode *prev = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->prev = 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 = head;
  new_node->prev = end;
  new_node->data = std::move(data);

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

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

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

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() {
  CircularList clist("Xenial");

  clist.insertNodeHead("Saucy");
  clist.insertNodeEnd("Quantal");

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

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

  return EXIT_SUCCESS;
}

Production:

node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal

L’algorithme général d’insertion d’éléments consiste à allouer un nouvel objet ListNode, à affecter des pointeurs de nœud correspondants à ses membres, puis à modifier les membres head/end selon les besoins. Nous incluons également une fonction printNodes pour afficher le contenu de la liste car nous pouvons avoir besoin d’inspecter l’exactitude du code. Notez qu’il ne faut pas oublier de désallouer toute la mémoire une fois que l’objet liste est hors de portée. Cette dernière fonction est implémentée en tant que destructeur.

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

Structure de données de liste doublement liée circulaire à partir de zéro en C++

Article connexe - C++ Data Structure