用 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