如何用C++实现双向循环链表

下面是如何用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;
}

上面的代码实现了链表的插入和删除操作，并展示了插入和删除操作后链表的遍历结果。