创建双向循环链表,实现双向循环链表的查询、插入和删除操作。
时间: 2024-10-13 09:17:02 浏览: 44
双向循环链表是一种特殊的链表结构,其中每个节点不仅包含指向下一个节点的指针(正向),还包含一个指向前一个节点的指针(反向)。这种结构常用于需要高效地进行双向遍历的情况。
下面是使用C++实现双向循环链表的基本步骤:
1. 定义节点结构:
```cpp
class Node {
public:
int data;
Node* next;
Node* prev;
};
```
`data`存储节点值,`next`指向下一个节点,`prev`指向前一个节点。对于循环链表,最后一个节点的`next`指向第一个节点,而第一个节点的`prev`也指向最后一个节点。
2. 创建链表:
```cpp
Node* createList() {
// 初始化链表为空或只有一个元素
Node* head = nullptr;
Node* tail = nullptr;
if (/* 插入数据 */){
// 添加新节点到链表尾部并更新头和尾指针
}
return head;
}
```
根据需求,在这里添加数据并确保形成循环。
3. 查询操作:
```cpp
bool find(int value, Node* current) {
while (current != nullptr) {
if (current->data == value) {
return true;
}
current = current->next; // 如果不是尾节点,继续前进
// 如果是尾节点,回到头开始搜索
else if (current == head) {
break;
}
}
return false;
}
```
查找指定值的功能会在当前节点及其前后节点之间进行。
4. 插入操作:
```cpp
void insert(int value) {
Node* newNode = new Node{value, head, tail};
if (head == nullptr) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
// 如果新节点是第一个,也需要更新头指针
if (newNode == head) {
head = newNode;
}
}
}
```
在这个函数中,如果链表为空,就新建一个头和尾节点;否则,新节点插入到尾部后成为新的尾节点。
5. 删除操作:
```cpp
void deleteNode(Node*& current, int value) {
if (current->data == value) {
if (current == head && current == tail) { // 删除头尾同时为该节点的情况
head = tail = nullptr;
} else if (current == head) { // 删除头节点
head = head->next;
head->prev = nullptr;
} else if (current == tail) { // 删除尾节点
tail->prev->next = nullptr;
tail = tail->prev;
} else { // 删除中间节点
current->prev->next = current->next;
current->next->prev = current->prev;
}
delete current; // 释放内存
} else {
current = current->next; // 未找到,移动到下一个节点
}
}
```
删除节点时要考虑特殊情况,如删除的是头节点或尾节点,以及普通情况。
阅读全文