Zirkuläre doppelt verkettete Liste in C++

Jinku Hu 12 Oktober 2023

C++ C++ Data Structure

Zirkuläre doppelt verkettete Liste in C++

In diesem Artikel wird gezeigt, wie eine zirkuläre doppelt verknüpfte Liste in C++ implementiert wird.

Zirkuläre doppelt verkettete Listendatenstruktur von Grund auf in C++

Eine doppelt verkettete Liste ist eine Datenstruktur, in der jeder Knoten Zeiger sowohl auf den nächsten als auch auf den vorherigen Knoten speichert. Dies macht es zur optimalen Wahl, std::deque-ähnliche Container zu implementieren. Es wäre besser, eine doppelt verkettete Liste kreisförmig zu machen, so dass das next Mitglied des letzten Knotens auf den Anfang der Liste zeigt und der erste Knoten auch auf den letzten Knoten wie sein vorheriger zeigt.

Zuerst müssen wir ein struct namens ListNode deklarieren, das zum Erstellen einer Liste verwendet wird. Als nächstes definieren wir eine Klasse CircularList mit zwei Datenelementen vom Typ ListNode* und dreielementigen Funktionen.

Beachten Sie, dass wir uns entschieden haben, nur einen Konstruktor einzuschließen, der einen string-Wert akzeptiert und den ersten Knoten initialisiert, aber dieser Teil kann nach Belieben des Programmierers geändert werden. Zwei Datenelemente - head und end – speichern den ersten und den letzten Knoten. Wir haben auch separate Funktionen zum Hinzufügen von Elementen auf jeder Seite der 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;
}

Ausgabe:

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

Der allgemeine Algorithmus zum Einfügen von Elementen besteht darin, ein neues ListNode-Objekt zuzuordnen, seinen Mitgliedern entsprechende Knotenzeiger zuzuweisen und dann die Elemente head/end nach Bedarf zu modifizieren. Wir fügen auch eine printNodes-Funktion hinzu, um den Listeninhalt anzuzeigen, da wir möglicherweise die Korrektheit des Codes überprüfen müssen. Beachten Sie, dass Sie nicht vergessen dürfen, den gesamten Speicher freizugeben, nachdem das Listenobjekt den Gültigkeitsbereich verlassen hat. Letztere Funktion ist als Destruktor implementiert.

Autor: 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

Zirkuläre doppelt verkettete Listendatenstruktur von Grund auf in C++

Verwandter Artikel - C++ Data Structure