数据结构初阶--带头双向循环链表

**数据结构初阶——带头双向循环链表**

在计算机科学中，数据结构是指组织和存储数据的方式。链表是一种常见的线性数据结构，它通过指针将元素连接起来。在本文中，我们将讨论带头双向循环链表（Circular Doubly Linked List）的基本概念、实现以及示例代码。

**什么是带头双向循环链表？**

带头双向循环链表是一种特殊的链表结构，它具有以下特点：

* 每个结点都有一个指向前驱结点（prev）的指针和一个指向后继结点（next）的指针。
* 链表形成一个环状结构，最后一个结点的next指针指向第一个结点。

**带头双向循环链表的操作**

带头双向循环链表支持以下基本操作：

* **插入**:在指定位置插入新元素。
* **删除**:从指定位置删除元素。
* **查找**:根据关键字查找元素。
* **遍历**:按照顺序访问所有元素。

**带头双向循环链表的实现**

下面是带头双向循环链表的基本实现代码：

cpp// 结点结构体struct Node {
 int data; // 元素值 Node* prev; // 前驱结点指针 Node* next; // 后继结点指针};

// 双向循环链表类class CircularDoublyLinkedList {
private:
 Node* head_; // 头结点指针public:
 // 构造函数 CircularDoublyLinkedList() : head_(nullptr) {}

 // 析构函数 ~CircularDoublyLinkedList() { clear(); }

 // 清空链表 void clear() {
 Node* current = head_;
 while (current != nullptr) {
 Node* next = current->next;
 delete current;
 current = next;
 }
 head_ = nullptr;
 }

 // 插入元素 void insert(int data, int position) {
 Node* newNode = new Node();
 newNode->data = data;

 if (head_ == nullptr) { // 链表为空，直接将新结点设为头结点 head_ = newNode;
 newNode->next = newNode;
 newNode->prev = newNode;
 } else {
 Node* current = head_;
 for (int i =0; i < position -1; ++i) { // 找到插入位置的前驱结点 current = current->next;
 }

 newNode->next = current->next;
 newNode->prev = current;
 newNode->next->prev = newNode;

 if (position ==0) { // 插入到头结点前 head_->prev = newNode;
 head_ = newNode;
 } else {
 current->next = newNode;
 }
 }
 }

 // 删除元素 void deleteNode(int position) {
 Node* current = head_;
 for (int i =0; i < position -1; ++i) { // 找到删除位置的前驱结点 current = current->next;
 }

 if (position ==0) { // 删除头结点 Node* next = head_->next;
 delete head_;
 head_ = next;
 head_->prev = head_;
 } else {
 Node* nodeToDelete = current->next;
 current->next = nodeToDelete->next;

 if (nodeToDelete == head_) { // 删除最后一个结点 head_->prev = current;
 }

 delete nodeToDelete;
 }
 }

 // 查找元素 bool find(int data) {
 Node* current = head_;
 do {
 if (current->data == data) return true; // 找到目标元素 current = current->next;
 } while (current != head_); // 遍历整个链表 return false; // 未找到目标元素 }

 // 遍历链表 void traverse() {
 Node* current = head_;
 do {
 std::cout << current->data << " ";
 current = current->next;
 } while (current != head_);
 std::cout << std::endl; // 输出结点值 }
};

cppint main() {
 CircularDoublyLinkedList list;

 // 插入元素 list.insert(10,0);
 list.insert(20,1);
 list.insert(30,2);

 // 输出链表内容 std::cout << "链表内容：";
 list.traverse();

 // 删除元素 list.deleteNode(1);

 // 输出链表内容 std::cout << "删除后链表内容：";
 list.traverse();

 return0;
}

链表内容：102030删除后链表内容：1030