在單向連結串列中插入節點 C++
Jinku Hu
2023年10月12日
本文講解了在 C++ 中如何在單向連結串列中插入新節點的方法。
實現在連結串列末尾插入節點的函式
連結串列是線性資料結構，由依次指向彼此的節點組成。在本文中，我們更多地關注單連結串列結構並相應地實現多個插入操作。
在單連結串列中，我們有一個資料物件和一個指向列表中下一個節點的指標。我們定義了一個名為 ListNode 的節點結構和兩個輔助函式（freeNodes 和 printNodes），以更好地演示列表插入操作。請注意，插入操作的時間複雜度因我們將節點插入到的位置而異。例如，如果列表末尾未知，則在列表末尾插入需要線性時間。
另一方面，在開頭插入一個新節點總是需要固定的時間。下面的程式碼演示了 insertNodeEnd 函式，它可以被視為構建列表的核心函式。它將列表的頭部作為第一個引數和需要儲存在新節點上的字串資料。該函式可以建立列表中的第一個元素並在其末尾附加新元素。該函式在空閒儲存記憶體上分配新節點。因此，需要 freeNodes 函式在程式退出之前釋放所有記憶體。
#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;
}
輸出：
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
實現一個函式在連結串列中的給定節點之後插入一個節點
在列表中間插入一個節點通常需要常數時間加上用於找到給定位置的搜尋演算法的時間複雜度。儘管如此，我們假設搜尋函式是單獨實現的，並構造了 insertNodeAfter 函式，以便需要將目標節點的位置作為第一個引數提供。
由於 insertNodeEnd 函式返回指向新新增節點的指標，我們利用其返回值來演示 insertNodeAfter 的操作。請記住，對於任意位置插入，你需要一個單獨的搜尋功能，甚至可能需要一個外部資料結構來在連結串列上實現更快的搜尋操作。
#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;
}
輸出：
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
實現在連結串列開頭插入節點的函式
單向連結串列的另一個有用的插入操作是在開頭附加一個新節點。該函式具有最佳執行時間 O(1)，因為始終儲存列表的頭部以訪問列表本身。insertNodeFront 函式獲取對根指標和需要儲存在節點上的 string 物件的引用。該過程被實現，以便你可以使用它來初始化一個新的連結串列以及前插入。
或者，你可以重寫函式以在 root 引數不是 nullptr 時分配一個新節點。否則，返回 nullptr 表示函式失敗。這些函式的介面取決於程式設計師的需要和 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;
}
輸出：
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
作者： Jinku Hu
