Einfügen eines Knotens in einfach verkettete Liste C++

  2. How-To's
  3. C++ Anleitungen
  4. Einfügen eines Knotens in einfach …
Jinku Hu 12 Oktober 2023
C++ C++ Data Structure
  1. Implementieren einer Funktion zum Einfügen eines Knotens am Ende einer verknüpften Liste
  2. Implementieren einer Funktion zum Einfügen eines Knotens nach einem gegebenen Knoten in einer verknüpften Liste
  3. Implementieren einer Funktion zum Einfügen eines Knotens am Anfang einer verknüpften Liste
Einfügen eines Knotens in einfach verkettete Liste C++

In diesem Artikel wird die Methode zum Einfügen eines neuen Knotens in eine einfach verknüpfte Liste in C++ erläutert.

Implementieren einer Funktion zum Einfügen eines Knotens am Ende einer verknüpften Liste

Verkettete Listen sind lineare Datenstrukturen, die aus sequentiell aufeinander zeigenden Knoten bestehen. In diesem Artikel konzentrieren wir uns mehr auf eine einfach verkettete Listenstruktur und implementieren entsprechend mehrere Einfügevorgänge.

In einer einfach verketteten Liste haben wir ein oder mehrere Datenobjekte und einen Zeiger auf den nächsten Knoten in der Liste. Wir haben eine Knotenstruktur namens ListNode und zwei Hilfsfunktionen (freeNodes und printNodes) definiert, um die Listeneinfügungsoperationen besser zu demonstrieren. Beachten Sie, dass die Zeitkomplexität des Einfügevorgangs abhängig von der Position variiert, an der wir einen Knoten einfügen. Das Einfügen am Ende der Liste dauert beispielsweise linear, wenn das Ende der Liste unbekannt ist.

Andererseits benötigt das Einfügen eines neuen Knotens am Anfang immer eine konstante Zeit. Der folgende Code demonstriert die Funktion insertNodeEnd, die als Kernfunktion zum Erstellen einer Liste behandelt werden kann. Es nimmt den Kopf der Liste als ersten Parameter und die string-Daten, die an einem neuen Knoten gespeichert werden müssen. Die Funktion kann das erste Element in der Liste erstellen und neue Elemente an dessen Ende anhängen. Die Funktion weist neue Knoten im freien Speicher zu. Daher wird die Funktion freeNodes benötigt, um den gesamten Speicher vor dem Beenden des Programms freizugeben.

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

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

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

struct ListNode *insertNodeEnd(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;
}

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;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeEnd(head, "Utopic");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Ausgabe:

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic

Implementieren einer Funktion zum Einfügen eines Knotens nach einem gegebenen Knoten in einer verknüpften Liste

Das Einfügen eines Knotens in die Mitte der Liste benötigt im Allgemeinen konstante Zeit plus die Zeitkomplexität des Suchalgorithmus, der verwendet wird, um die gegebene Position zu finden. Wir gehen jedoch davon aus, dass die Suchfunktion separat implementiert ist und konstruieren die Funktion insertNodeAfter so, dass als erstes Argument die Position des Zielknotens übergeben werden muss.

Da die Funktion insertNodeEnd den Zeiger auf einen neu angehängten Knoten zurückgibt, verwenden wir dessen Rückgabewert, um die Funktionsweise von insertNodeAfter zu demonstrieren. Denken Sie daran, dass Sie für beliebige Positionseinfügungen eine separate Suchfunktion benötigen und möglicherweise sogar eine externe Datenstruktur benötigen, um eine schnellere Suchoperation in einer verknüpften Liste zu implementieren.

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

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

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

struct ListNode *insertNodeEnd(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;
}

struct ListNode *insertNodeAfter(struct ListNode *prev, string data) {
  if (!prev) return nullptr;

  auto new_node = new ListNode;
  new_node->next = nullptr;
  new_node->data = std::move(data);
  prev->next = new_node;
  return new_node;
}

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;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  auto iter = insertNodeEnd(head, "Utopic");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeAfter(iter, "Xenial");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Ausgabe:

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
node 5 - data: Xenial

Implementieren einer Funktion zum Einfügen eines Knotens am Anfang einer verknüpften Liste

Eine weitere nützliche Einfügeoperation für die einfach verkettete Liste ist das Anhängen eines neuen Knotens am Anfang. Diese Funktion hat die beste Laufzeit O(1), da immer der Kopf der Liste gespeichert wird, um auf die Liste selbst zuzugreifen. Die Funktion insertNodeFront nimmt die Referenz auf einen Wurzelzeiger und das string-Objekt, das auf dem Knoten gespeichert werden muss. Der Prozess ist so implementiert, dass Sie ihn sowohl zum Initialisieren einer neuen verketteten Liste als auch zum Fronteinfügen verwenden können.

Alternativ können Sie die Funktion umschreiben, um einen neuen Knoten zuzuweisen, wenn das Argument root nicht nullptr ist. Andernfalls geben Sie nullptr zurück, um anzuzeigen, dass die Funktion fehlgeschlagen ist. Die Schnittstelle dieser Funktionen richtet sich nach den Bedürfnissen der Programmierer und der Struktur des ListNode.

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

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

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

struct ListNode *insertNodeEnd(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;
}

struct ListNode *insertNodeFront(struct ListNode *&root, string data) {
  auto new_node = new ListNode;
  if (root) {
    new_node->next = root;
    new_node->data = std::move(data);
    root = new_node;
    return root;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

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;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeFront(head, "Bionic");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Ausgabe:

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
Autor: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

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

Verwandter Artikel - C++ Data Structure