Implementieren einer doppelt verknüpften Liste in C++

1. Verwenden Sie struct, um Double Linked List in C++ zu implementieren
2. Verwendung von den Container std::list als doppelt verknüpfte Liste in C++

In diesem Artikel werden mehrere Methoden zum Implementieren einer doppelt verknüpften Liste in C++ veranschaulicht.

Verwenden Sie struct, um Double Linked List in C++ zu implementieren

Verknüpfte Listen gelten als eine der gebräuchlichsten Datenstrukturen, denen Sie in der Programmierung begegnen können. Diese Strukturen sind in dem Sinne verknüpft, dass jeder Knoten die Adresse eines anderen enthält. Es gibt zwei Arten von verknüpften Listen: einfach verknüpfte Listen und doppelt verknüpfte Listen. Eine einfach verknüpfte Liste enthält Knoten, die nur auf den nächsten Knoten in der Liste zeigen; somit macht es die Durchquerung der Struktur in eine Richtung. Andererseits bieten doppelt verkettete Listen einen bidirektionalen Zugriff von jedem Knoten in der Liste.

In diesem Fall implementieren wir eine doppelt verkettete Liste mit dem Befehl struct, machen alle ihre Datenelemente öffentlich und definieren die Funktionen zur Elementmanipulation separat. Beachten Sie, dass man eine objektorientierte Version mit Elementfunktionen bevorzugen kann, die die Elementmanipulationsroutinen und einige Datenelemente zur Aufzeichnung von Daten bereitstellen.

Der folgende Beispielcode enthält den Treibercode in der Funktion main, die das grundlegende Nutzungsszenario testet, bei dem die Vektorelemente string in eine Liste eingefügt und dann die Liste freigegeben wird. Wir verwenden den Operator new, um jeden Knoten dynamisch zuzuweisen, und folglich iteriert die Funktion freeNodes durch die Liste, um auf jedem Node delete aufzurufen.

Das Verfahren des separaten Zuweisens jedes Node könnte ineffizient sein, wenn der Benutzer eine relativ leistungsstarke Struktur mit verknüpften Listen entwerfen möchte. Man könnte eine Massenzuweisung von Speicherressourcen in Betracht ziehen, um schnell neue Knoten hinzuzufügen und, wenn sie nicht benötigt werden, mehrere gleichzeitig freizugeben. In diesem Design beginnen wir mit dem Erstellen der Liste mit dem gültigen Element, das den ersten Knoten in der Struktur darstellt. Einige Implementierungen können ein Dummy-Element erstellen, das den Kopf der Liste bezeichnet, aber keine Elementdaten enthält.

#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;
}

Ausgabe:

data: Rocket Lake
data: Meteor Lake

Sie können verknüpfte Listen als Bausteine ​​für spezialisiertere Datenstrukturen wie Stapel, Deques, Warteschlangen oder zirkuläre Listen verwenden. Letzteres ist interessant, da es sich im Wesentlichen um eine doppelt verkettete Liste handelt, bei der der letzte Knoten als nächster Knoten auf das erste Element zeigt und entsprechend der erste auf das letzte Element als vorheriger Knoten zeigt. Beachten Sie, dass der folgende Codeausschnitt die Funktion printNodes hinzufügt, um den Inhalt jedes Knotens in der erstellten Liste anzuzeigen.

#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;
}

Ausgabe:

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

Verwendung von den Container std::list als doppelt verknüpfte Liste in C++

Alternativ kann man den Container std::list aus C++ STL verwenden, der normalerweise als doppelt verkettete Liste implementiert ist und verschiedene Funktionen zur Elementmanipulation bereitstellt. Darüber hinaus ist der Container std::list implementiert, um recht leistungsfähige Algorithmen zu unterstützen, die in der Standardbibliothek enthalten sind, sodass der Benutzer Zeit bei der Entwicklung sparen kann, wenn einige sehr spezielle Leistungsmerkmale nicht erforderlich sind.

#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;
}

Ausgabe:

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