C++零基础精通数据结构之带头双向循环链表

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

带头双向循环链表是一个常见的数据结构，它可以用来实现链表和队列等数据结构。带头双向循环链表的特点是：

1. 每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。
2. 链表中有一个头节点，但是它不存储数据。
3. 链表的尾节点指向头节点，头节点的前一个节点指向链表的尾节点。这样就形成了一个循环。

怎样实现带头双向循环链表？

带头双向循环链表的节点结构体

struct Node {
    int data;
    Node* prev;
    Node* next;
};

节点包含一个数据域 data，以及两个指针 prev 和 next。

初始化带头双向循环链表

Node* init() {
    Node* head = new Node;         // 创建头节点
    head->prev = head;            // 头节点的上一个节点是头节点自身
    head->next = head;            // 头节点的下一个节点是头节点自身
    return head;                  // 返回头节点
}

初始化带头双向循环链表，先创建一个头节点，然后让头节点的上一个指针和下一个指针都指向自身，最后返回头节点。

判断带头双向循环链表是否为空

bool isEmpty(Node* head) {
    return head->next == head;
}

如果头节点的下一个节点指向头节点自身，说明链表为空，返回 true。

在带头双向循环链表尾部插入一个节点

void insertAtTail(Node* head, int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->prev = head->prev;   // 新节点的上一个节点是原链表的尾节点
    newNode->next = head;         // 新节点的下一个节点是头节点
    head->prev->next = newNode;   // 原链表的尾节点的下一个节点是新节点
    head->prev = newNode;         // 头节点的上一个节点是新节点
}

创建一个新节点，将它的数据域和上一个指针赋值，然后将它的下一个指针指向头节点，接着将原链表的尾节点的下一个指针指向新节点，最后将头节点的上一个指针指向新节点。

在带头双向循环链表头部插入一个节点

void insertAtHead(Node* head, int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->prev = head;         // 新节点的上一个节点是头节点
    newNode->next = head->next;   // 新节点的下一个节点是原链表的头节点
    head->next->prev = newNode;   // 原链表的头节点的上一个节点是新节点
    head->next = newNode;         // 头节点的下一个节点是新节点
}

创建一个新节点，将它的数据域和下一个指针赋值，然后将它的上一个指针指向头节点，接着将原链表的头节点的上一个指针指向新节点，最后将头节点的下一个指针指向新节点。

删除节点

void remove(Node* head, int data) {
    Node* p = head->next;
    while (p != head && p->data != data) {   // 找到要删除的节点
        p = p->next;
    }
    if (p != head) {
        p->prev->next = p->next;   // 上一个节点的下一个指针指向下一个节点
        p->next->prev = p->prev;   // 下一个节点的上一个指针指向上一个节点
        delete p;                  // 释放被删除的节点的内存
    }
}

先找到要删除的节点，然后将它的上一个节点的下一个指针指向它的下一个节点，将它的下一个节点的上一个指针指向它的上一个节点，最后释放它的内存。

示例说明

示例1：插入数据、遍历数据、删除数据

int main() {
    Node* head = init();                  // 初始化带头双向循环链表
    insertAtTail(head, 1);                // 在尾部插入1
    insertAtTail(head, 2);                // 在尾部插入2
    insertAtHead(head, 0);                // 在头部插入0
    insertAtTail(head, 3);                // 在尾部插入3
    insertAtTail(head, 4);                // 在尾部插入4

    Node* p = head->next;                 // 遍历链表
    while (p != head) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    remove(head, 1);                      // 删除1

    p = head->next;                       // 遍历链表
    while (p != head) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    return 0;
}

输出结果：

0 1 2 3 4
0 2 3 4

示例2：插入数据、判断链表是否为空

int main() {
    Node* head = init();                  // 初始化带头双向循环链表
    insertAtTail(head, 1);                // 在尾部插入1
    insertAtTail(head, 2);                // 在尾部插入2

    if (isEmpty(head)) {                  // 判断链表是否为空
        cout << "链表为空" << endl;
    } else {
        cout << "链表不为空" << endl;
    }

    return 0;
}

输出结果：

链表不为空

至此，带头双向循环链表的初始化、插入、删除、遍历和判断是否为空的基本操作都已经讲解完毕。