08 - 线性表的类型定义 - 循环双向链表

**线性表的类型定义**

在计算机科学中，线性表是指一种数据结构，它的元素按照一定的顺序排列起来。线性表可以是单向链表，也可以是双向链表或循环双向链表。在本文中，我们将讨论如何定义一个循环双向链表。

**什么是循环双向链表**

循环双向链表是一种特殊的双向链表，它的最后一个元素指向第一个元素，形成一个环形结构。这种数据结构在某些应用场景下非常有用，比如说，需要快速查找和插入数据的场合。

**循环双向链表的类型定义**

我们可以使用以下C++代码来定义一个循环双向链表：

cpp// 定义一个循环双向链表结点结构体struct Node {
 int data; // 结点中的数据 Node* prev; // 前驱结点指针 Node* next; // 后继结点指针};

// 定义一个循环双向链表类class CircularDoublyLinkedList {
private:
 Node* head; // 头结点指针 int size; // 链表中的元素数量public:
 // 构造函数 CircularDoublyLinkedList() : head(nullptr), size(0) {}

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

 // 清空链表 void clear() {
 while (head != nullptr) {
 Node* temp = head;
 head = head->next;
 delete temp;
 }
 size =0;
 }

 // 插入结点到头部 void insertHead(int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->prev = nullptr;
 if (head == nullptr) {
 head = newNode;
 newNode->next = head; // 形成环形结构 } else {
 newNode->next = head;
 head->prev = newNode;
 head = newNode;
 }
 size++;
 }

 // 插入结点到尾部 void insertTail(int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 if (head == nullptr) {
 head = newNode;
 newNode->prev = head; // 形成环形结构 } else {
 Node* temp = head;
 while (temp->next != head) {
 temp = temp->next;
 }
 temp->next = newNode;
 newNode->prev = temp;
 newNode->next = head; // 形成环形结构 }
 size++;
 }

 // 删除头结点 void deleteHead() {
 if (head == nullptr) return;
 Node* temp = head;
 head = head->next;
 head->prev = nullptr;
 delete temp;
 size--;
 }

 // 删除尾结点 void deleteTail() {
 if (head == nullptr) return;
 Node* temp = head;
 while (temp->next != head) {
 temp = temp->next;
 }
 temp->prev->next = head; // 形成环形结构 delete temp;
 size--;
 }

 // 获取链表中的元素数量 int getSize() const {
 return size;
 }

 // 获取头结点的数据 int getHeadData() const {
 if (head == nullptr) return -1; // 头结点不存在 return head->data;
 }
};

cppint main() {
 CircularDoublyLinkedList list;

 // 插入头结点 list.insertHead(10);
 list.insertHead(20);

 // 获取链表中的元素数量 std::cout << "链表中元素数量：" << list.getSize() << std::endl;

 // 删除头结点 list.deleteHead();

 // 获取链表中的元素数量 std::cout << "链表中元素数量：" << list.getSize() << std::endl;

 return0;
}