用 C++ 實現雙向連結串列
本文將演示如何在 C++ 中實現雙向連結串列的多種方法。
使用 struct 在 C++ 中實現雙向連結串列
連結串列被認為是程式設計中最常見的資料結構之一。這些結構是相互關聯的，每個節點都包含另一個節點的地址。連結串列有兩種型別：單連結串列和雙向連結串列。單向連結串列包含僅指向列表中下一個節點的節點；因此，它使結構的遍歷是單向的。另一方面，雙向連結串列提供了從列表中每個節點的雙向訪問。
在這種情況下，我們使用 struct 命令實現一個雙向連結串列，將其所有資料成員公開並分別定義元素操作函式。請注意，人們可能更喜歡具有提供元素操作例程和一些記錄儲存資料成員的成員函式的物件導向版本。
以下示例程式碼包含 main 函式中的驅動程式程式碼，用於測試基本使用場景，其中將 string 向量元素插入到列表中，然後釋放列表。我們利用 new 操作符動態分配每個節點，因此，freeNodes 函式遍歷列表以在每個 Node 上呼叫 delete。
如果使用者想要設計一個相對高效能的連結串列結構，單獨分配每個 Node 的方法可能效率低下。人們可能會考慮大量分配記憶體資源以快速新增新節點，並在不需要時同時釋放多個節點。在此設計中，我們開始使用表示結構中第一個節點的有效元素構建列表。一些實現可能會建立一個虛擬元素，它表示列表的頭部但不包含元素資料。
#include<iostream>
#include<string>
#include<vector>
using std::cout; using std::cin;
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;
}
輸出：
data: Rocket Lake
data: Meteor Lake
你可以將連結串列用作更專業的資料結構（如堆疊、雙端佇列、佇列或迴圈列表）的構建塊。後者很有趣，因為它本質上是一個雙向連結串列，其中最後一個節點指向第一個元素作為下一個節點，相應地第一個指向最後一個元素作為前一個節點。請注意，以下程式碼片段新增了 printNodes 函式以顯示構造列表中每個節點的內容。
#include<iostream>
#include<string>
#include<vector>
using std::cout; using std::cin;
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;
}
輸出：
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
在 C++ 中使用 std::list 容器作為雙向連結串列
或者，可以使用 C++ STL 中的 std::list 容器，它通常實現為雙向連結串列並提供各種元素操作功能。此外，std::list 容器的實現是為了支援標準庫中包含的非常強大的演算法，因此如果不需要一些非常特殊的效能特徵，使用者可以節省開發時間。
#include<iostream>
#include<string>
#include<list>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::list;
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;
}
輸出：
0; 1; 2; 3; 4; 5;
0; 1; 2; 99; 3; 4; 5;
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