双向循环链表是一种特殊的链表结构，它既有前驱指针又有后继指针，并且链表的头尾相连形成一个环。带头节点的双向循环链表在实现上更加方便，因为头节点可以作为哨兵节点，简化边界条件的处理。本文将详细介绍如何使用C++实现一个带头节点的双向循环链表。
双向循环链表的每个节点包含三个部分： - 数据域：存储节点的数据。 - 前驱指针：指向当前节点的前一个节点。 - 后继指针：指向当前节点的下一个节点。
带头节点的双向循环链表在初始化时，头节点的前驱和后继指针都指向自己，形成一个空链表。
首先，我们需要定义一个节点类 Node，用于表示链表中的每个节点。
计算
安全
数据库
网络和加速
企业服务
template <typename T>
class Node {
public:
T data; // 数据域
Node* prev; // 前驱指针
Node* next; // 后继指针
// 构造函数
Node(T value) : data(value), prev(nullptr), next(nullptr) {}
};
接下来，我们定义一个双向循环链表类 DoublyCircularLinkedList，它包含一个头节点和一些基本的操作函数。
template <typename T>
class DoublyCircularLinkedList {
private:
Node<T>* head; // 头节点
public:
// 构造函数
DoublyCircularLinkedList() {
head = new Node<T>(T()); // 创建头节点
head->prev = head; // 头节点的前驱指向自己
head->next = head; // 头节点的后继指向自己
}
// 析构函数
~DoublyCircularLinkedList() {
clear(); // 清空链表
delete head; // 删除头节点
}
// 清空链表
void clear() {
Node<T>* current = head->next;
while (current != head) {
Node<T>* temp = current;
current = current->next;
delete temp;
}
head->prev = head;
head->next = head;
}
// 在链表尾部插入节点
void push_back(T value) {
Node<T>* newNode = new Node<T>(value);
Node<T>* last = head->prev;
last->next = newNode;
newNode->prev = last;
newNode->next = head;
head->prev = newNode;
}
// 在链表头部插入节点
void push_front(T value) {
Node<T>* newNode = new Node<T>(value);
Node<T>* first = head->next;
head->next = newNode;
newNode->prev = head;
newNode->next = first;
first->prev = newNode;
}
// 删除链表尾部的节点
void pop_back() {
if (head->prev == head) return; // 链表为空
Node<T>* last = head->prev;
Node<T>* newLast = last->prev;
newLast->next = head;
head->prev = newLast;
delete last;
}
// 删除链表头部的节点
void pop_front() {
if (head->next == head) return; // 链表为空
Node<T>* first = head->next;
Node<T>* newFirst = first->next;
head->next = newFirst;
newFirst->prev = head;
delete first;
}
// 打印链表
void print() const {
Node<T>* current = head->next;
while (current != head) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
下面是一个简单的示例，展示了如何使用 DoublyCircularLinkedList 类。
int main() {
DoublyCircularLinkedList<int> list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.print(); // 输出: 1 2 3
list.push_front(0);
list.print(); // 输出: 0 1 2 3
list.pop_back();
list.print(); // 输出: 0 1 2
list.pop_front();
list.print(); // 输出: 1 2
return 0;
}
本文介绍了如何使用C++实现一个带头节点的双向循环链表。通过定义节点类和链表类，我们可以方便地实现链表的基本操作，如插入、删除和打印等。带头节点的设计简化了边界条件的处理，使得链表的操作更加直观和高效。希望本文对你理解双向循环链表的实现有所帮助。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
