Löschen eines Knotens in einer verketteten Liste in C++

Jinku Hu 12 Oktober 2023

C++ C++ Data Structure

Löschen eines Knotens in einer verketteten Liste in C++

In diesem Artikel wird die Methode zum Implementieren einer Funktion erläutert, die einen bestimmten Knoten in einer verknüpften Liste von C++ löscht.

Implementieren einer Funktion zum Löschen eines bestimmten Knotens in einer verknüpften Liste

In diesem Artikel implementieren wir eine einfach verkettete Liste von Grund auf, ohne die Container von STL zu verwenden. Daher müssen wir einige notwendige Funktionen definieren, um Knoten in einer verknüpften Liste zu verwalten.

Das Element insertNode ist die Kernfunktion, die aufgerufen werden muss, um eine neue verknüpfte Liste zu erstellen. Da wir den Kopf der Liste speichern müssen, gibt der insertNode den Zeiger auf den Knoten vom Typ ListNode zurück. Letzteres ist die minimale Darstellung des verknüpften Listenknotens. Es enthält lediglich einen Zeiger auf den nächsten Knoten und das Datenobjekt string.

Während des Testens und der Demonstration des Programms ist es wichtig, einige Hilfsfunktionen zu haben, um einige Meldungen auf der Benutzerkonsole anzuzeigen. In diesem Fall wird das Element printNodes verwendet, um alle Knoten in der gegebenen Listenstruktur zu drucken. Außerdem müssen wir bei der Zuweisung neuer Knoten im dynamischen Speicher beim Beenden des Programms mit der Funktion freeNodes jeden vorhandenen Knoten in der Liste freigeben.

Sobald wir eine Liste mit den beliebigen Daten erstellt haben, wie in der Funktion main des folgenden Code-Schnipsels gezeigt, können wir deleteNode aufrufen, das die Operation zum Entfernen des Knotens implementiert. Das Entfernen eines Knotens erfordert die Bearbeitung mehrerer Eckfälle darin. Nämlich das Szenario, wenn der gegebene Knoten der gleiche ist wie der Kopf der Liste und das andere, wenn der gegebene Knoten der einzige Knoten in der Liste ist.

Im letzteren Szenario können wir einfach den delete-Operator auf dem Knotenzeiger aufrufen und von der Funktion zurückkehren. Es ist jedoch wichtig, der Adresse nullptr zuzuweisen, da dies uns hilft, der gleichen head-Variablen in der Hauptfunktion neue Elemente hinzuzufügen.

Andererseits ist es relativ schwierig, den Kopfknoten zu entfernen, wenn andere Knoten in der Liste vorhanden sind. Wir müssen den Inhalt des zweiten Knotens in den Kopfknoten kopieren und den vorherigen löschen. Beachten Sie, dass jeder Fall den Wert EXIT_SUCCESS zurückgibt, um einen erfolgreichen Funktionsaufruf anzuzeigen.

#include <iostream>
#include <string>

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

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNode(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

int deleteNode(struct ListNode *root, struct ListNode *node) {
  if (node == nullptr || root == nullptr) return EXIT_FAILURE;

  if (root == node) {
    if (root->next == nullptr) {
      delete node;
      root = nullptr;
      return EXIT_SUCCESS;
    }

    node = root->next;
    root->data = root->next->data;
    root->next = root->next->next;
    delete node;
    return EXIT_SUCCESS;
  }

  auto prev = root;
  while (prev->next != node && prev->next != nullptr) {
    prev = prev->next;
  }

  prev->next = node->next;
  delete node;
  return EXIT_SUCCESS;
}

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

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

int main() {
  struct ListNode *head = nullptr;

  head = insertNode(head, "Xenial");

  insertNode(head, "Artful");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  deleteNode(head, head);
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Ausgabe:

node 0 - data: Xenial
node 1 - data: Artful
 -----------------------------------
node 0 - data: Artful

Der verbleibende Funktionscode implementiert den regulären Fall, bei dem der angegebene Knoten aus der Listenkette ausgehängt und dann mit dem Operator delete freigegeben wird. Beachten Sie jedoch, dass diese Operation erfordert, dass der vorherige Knoten gefunden wird, was die lineare Zeitoperation für jeden Knoten außer dem Kopf der Liste ist. Normalerweise sollte man das Ende der Liste in der verketteten Listenstruktur speichern, um die konstante Zeitentfernung für das Ende der Liste zu gewährleisten.

Der folgende Codeausschnitt zeigt ein anderes Szenario der main-Funktion, bei dem ein Knoten aus der Mitte der Liste entfernt wird.

#include <iostream>
#include <string>

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

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNode(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

int deleteNode(struct ListNode *root, struct ListNode *node) {
  if (node == nullptr || root == nullptr) return EXIT_FAILURE;

  if (root == node) {
    if (root->next == nullptr) {
      delete node;
      root = nullptr;
      return EXIT_SUCCESS;
    }

    node = root->next;
    root->data = root->next->data;
    root->next = root->next->next;
    delete node;
    return EXIT_SUCCESS;
  }

  auto prev = root;
  while (prev->next != node && prev->next != nullptr) {
    prev = prev->next;
  }

  prev->next = node->next;
  delete node;
  return EXIT_SUCCESS;
}

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

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

int main() {
  struct ListNode *head = nullptr;

  head = insertNode(head, "Xenial");

  auto iter = insertNode(head, "Bionic");
  insertNode(head, "Artful");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  deleteNode(head, iter);
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Ausgabe:

node 0 - data: Xenial
node 1 - data: Bionic
node 2 - data: Artful
 -----------------------------------
node 0 - data: Xenial
node 1 - data: Artful

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

Implementieren einer Funktion zum Löschen eines bestimmten Knotens in einer verknüpften Liste

Verwandter Artikel - C++ Data Structure