C++ 中的循环双向链表
Jinku Hu
2023年10月12日
本文将演示如何在 C++ 中实现循环双向链表。
C++ 中从头开始的循环双向链表数据结构
双向链表是一种数据结构，其中每个节点都存储指向下一个和前一个节点的指针。这使其成为实现 std::deque 类容器的最佳选择。最好制作一个双向链表循环，以便最后一个节点的 next 成员指向列表的开头，第一个节点也指向最后一个节点作为它的前一个节点。
首先，我们需要声明一个名为 ListNode 的 struct，用于构造一个列表。接下来，我们定义一个 CircularList 类，其中包含两个类型为 ListNode* 的数据成员和三个成员函数。
请注意，我们决定只包含一个接受 string 值并初始化第一个节点的构造函数，但这部分可以根据程序员的需要进行修改。两个数据成员 - head 和 end - 存储第一个和最后一个节点。我们还有单独的函数来在列表的每一侧添加元素。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
struct ListNode *prev = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->prev = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
ListNode *insertNodeHead(string data);
void printNodes();
~CircularList();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
end = end->next;
return end;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
head = new_node;
return head;
}
CircularList::~CircularList() {
while (head != end) {
auto tmp = head;
head = head->next;
delete tmp;
}
delete head;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
CircularList clist("Xenial");
clist.insertNodeHead("Saucy");
clist.insertNodeEnd("Quantal");
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.printNodes();
return EXIT_SUCCESS;
}
输出：
node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
-----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal
元素插入的一般算法需要分配一个新的 ListNode 对象，将相应的节点指针分配给其成员，然后根据需要修改 head/end 成员。我们还包括一个 printNodes 函数来显示列表内容，因为我们可能需要检查代码的正确性。请注意，在列表对象超出范围后，一定不要忘记释放所有内存。后一个函数是作为析构函数实现的。
作者： Jinku Hu
