下面是如何用C++实现双向循环链表的完整攻略。
什么是双向循环链表
双向循环链表是一种常见的数据结构,其将每个节点都视为一个对象,一个节点除了存储自己的数据外,还会保存一个指向前一个节点和后一个节点的指针,因此可以用来表示一系列数据的集合。
在双向循环链表中,最后一个节点的指针指向第一个节点,第一个节点的指针指向最后一个节点,这种结构称为循环链表。而双向链表的特点是每个节点有两个指针,一个指针指向前一个节点,一个指针指向后一个节点。
如何实现
定义结构体
C++ 代码实现双向循环链表需要定义链表节点的结构,这里我们采用结构体的方式来定义。
struct ListNode {
int val;
ListNode* prev;
ListNode* next;
ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
在上面的代码中,我们定义了一个名为 ListNode
的结构体,其中包含了一个整数类型的 val
字段,一个指向前一个节点的指针 prev
,一个指向后一个节点的指针 next
。同时,我们为该结构体提供了一个构造函数,用来初始化节点数据。
实现插入操作
节点插入是链表的一个核心操作,它可以用来添加新的节点到链表中。
void insert(ListNode* &head, ListNode* &tail, ListNode* node) {
if (head == nullptr) {
head = node;
tail = node;
head->prev = tail;
tail->next = head;
return;
}
node->next = head;
node->prev = tail;
head->prev = node;
tail->next = node;
tail = node;
}
在上面的代码中,我们定义了一个 insert
函数,它接收三个参数:链表的头指针 head
、链表的尾指针 tail
和要插入的新节点 node
。
当链表为空时,插入的节点即为头节点,同时也是尾节点。因此我们需要将头指针和尾指针都指向插入的节点,并将插入的节点指向自身作为下一个节点和上一个节点。
当链表不为空时,我们将插入的节点插入到链表的末尾,并将它的前驱和后继指针指向链表的头尾节点。
实现删除操作
节点删除是链表的另一个核心操作,它可以用来删除链表中的指定节点。
void erase(ListNode* &head, ListNode* &tail, ListNode* node) {
if (head == nullptr || node == nullptr) {
return;
}
if (head == tail && head == node) {
delete node;
head = nullptr;
tail = nullptr;
return;
}
if (node == head) {
head = node->next;
head->prev = tail;
tail->next = head;
delete node;
return;
}
if (node == tail) {
tail = node->prev;
tail->next = head;
head->prev = tail;
delete node;
return;
}
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
}
在上面的代码中,我们定义了一个 erase
函数,它接收三个参数:链表的头指针 head
、链表的尾指针 tail
和要删除的节点 node
。
在删除节点之前,我们需要先判断链表是否为空以及要删除的节点是否存在。当链表为空或要删除的节点不存在时,直接返回。
当要删除的节点是头尾节点时,我们需要判断删除的节点是否是链表唯一的一个节点,如果是唯一的节点,则将头指针和尾指针都置空;否则,将头指针或尾指针指向该节点的下一个或上一个节点。
当要删除的节点是中间节点时,我们需要将节点的上一个节点的后继指针指向它的下一个节点,将节点的下一个节点的前驱指针指向它的上一个节点,最后删除该节点即可。
示例代码
下面给出两个示例代码,分别展示如何实现双向循环链表的插入和删除操作。
#include <iostream>
struct ListNode {
int val;
ListNode* prev;
ListNode* next;
ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
void insert(ListNode* &head, ListNode* &tail, ListNode* node) {
if (head == nullptr) {
head = node;
tail = node;
head->prev = tail;
tail->next = head;
return;
}
node->next = head;
node->prev = tail;
head->prev = node;
tail->next = node;
tail = node;
}
void erase(ListNode* &head, ListNode* &tail, ListNode* node) {
if (head == nullptr || node == nullptr) {
return;
}
if (head == tail && head == node) {
delete node;
head = nullptr;
tail = nullptr;
return;
}
if (node == head) {
head = node->next;
head->prev = tail;
tail->next = head;
delete node;
return;
}
if (node == tail) {
tail = node->prev;
tail->next = head;
head->prev = tail;
delete node;
return;
}
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
}
int main() {
ListNode* head = nullptr;
ListNode* tail = nullptr;
insert(head, tail, new ListNode(1));
insert(head, tail, new ListNode(2));
insert(head, tail, new ListNode(3));
ListNode* cur = head;
std::cout << "正向遍历:" << std::endl;
for (int i = 0; i < 3; ++i) {
std::cout << cur->val << std::endl;
cur = cur->next;
}
std::cout << "反向遍历:" << std::endl;
for (int i = 0; i < 3; ++i) {
std::cout << cur->val << std::endl;
cur = cur->prev;
}
erase(head, tail, head);
erase(head, tail, tail);
cur = head;
std::cout << "正向遍历:" << std::endl;
while (cur) {
std::cout << cur->val << std::endl;
cur = cur->next;
}
std::cout << "反向遍历:" << std::endl;
cur = tail;
while (cur) {
std::cout << cur->val << std::endl;
cur = cur->prev;
}
return 0;
}
上面的代码实现了链表的插入和删除操作,并展示了插入和删除操作后链表的遍历结果。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:如何用C++实现双向循环链表 - Python技术站