用 C++ 刪除連結串列中的節點

Jinku Hu 2023年10月12日
用 C++ 刪除連結串列中的節點

本文將討論如何在連結串列 C++ 中實現刪除給定節點的函式的方法。

實現刪除連結串列中給定節點的函式

在本文中,我們從頭開始實現一個單向連結串列,而不使用 STL 中的容器。因此,我們需要定義一些必要的函式來管理連結串列中的節點。

insertNode 元素是建立新連結串列需要呼叫的核心函式。由於我們需要儲存列表的頭部,insertNode 返回指向 ListNode 型別節點的指標。後者是連結串列節點的最小表示。它只包含一個指向下一個節點的指標和 string 資料物件。

在程式的測試和演示過程中,重要的是要有一些實用函式來向使用者控制檯顯示一些訊息。在這種情況下,printNodes 元素用於列印給定列表結構中的所有節點。此外,在動態記憶體上分配新節點時,我們需要使用 freeNodes 函式在程式退出時釋放列表中的每個現有節點。

一旦我們構建了一個包含任意資料的列表,如以下程式碼片段的 main 函式所示,我們就可以呼叫 deleteNode,它實現節點刪除操作。節點的移除需要在其中處理幾個極端情況。即,當給定節點與列表的頭部相同時的場景,當給定節點是列表中的唯一節點時的另一個場景。

在後一種情況下,我們可以在節點指標上呼叫 delete 運算子並從函式返回。儘管將 nullptr 分配給地址很重要,因為這將幫助我們將新元素新增到 main 函式中的同一個 head 變數中。

另一方面,當連結串列中還有其他節點時,移除頭節點是比較棘手的。我們必須將第二個節點的內容複製到頭節點並刪除前一個。請注意,每個案例都返回 EXIT_SUCCESS 值以指示成功的函式呼叫。

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

輸出:

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

其餘的函式程式碼實現了常規情況,其中給定節點從列表鏈中解開,然後使用 delete 運算子解除分配。但是請注意,此操作需要找到前一個節點,這是對除列表頭部之外的每個節點的線性時間操作。通常,為了保證連結串列末尾的恆定時間移除,應該將連結串列的末尾儲存在連結串列結構中。

下面的程式碼片段演示了一個不同的 main 函式場景,其中從列表中間刪除了一個節點。

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

輸出:

node 0 - data: Xenial
node 1 - data: Bionic
node 2 - data: Artful
 -----------------------------------
node 0 - data: Xenial
node 1 - data: Artful
作者: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

DelftStack.com 創辦人。Jinku 在機器人和汽車行業工作了8多年。他在自動測試、遠端測試及從耐久性測試中創建報告時磨練了自己的程式設計技能。他擁有電氣/ 電子工程背景,但他也擴展了自己的興趣到嵌入式電子、嵌入式程式設計以及前端和後端程式設計。

LinkedIn Facebook

相關文章 - C++ Data Structure