C++ 中的循环双向链表
Jinku Hu
2023年10月12日
![C++ 中的循环双向链表](/img/Cpp/feature-image---circular-doubly-linked-list-in-cpp.webp)
本文将演示如何在 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