迹忆客 专注技术分享

循环双向链表是循环链表和双向链表的组合。它的两个节点由上一个和下一个指针连接。最后一个节点的下一个指针指向第一个节点，第一个节点的上一个指针指向最后一个节点。它可以从两个方向遍历，也可以从尾巴到头部或从头到尾跳跃。它还用于实现高级数据结构，如斐波那契堆。

循环双向链表遍历

我们只需检查迭代中的下一个节点不是 head 的条件，然后遍历循环双向链表，然后根据向前/向后将 temp 从 temp->next 或 temp->prev 中移出迭代。

正向

令 head 成为链接列表的第一个节点。

• 初始化指向链接列表的 head 节点的 curr。
• 尽管 curr 尚未到达列表的末尾，即 curr->next！=head，请执行以下操作：
  • 打印存储在当前节点内的数据。
  • curr=curr->next;

同样，我们可以通过从 tail 开始并将 curr 更改为 curr->prev 来进行向后遍历。

反向

令 tail（即 head->prev）成为链接列表的最后一个节点。

• 初始化 curr，指向链接列表的 tail 节点。
• 尽管 curr 尚未到达列表的开头，即 curr->prev!=tail，请执行以下操作：
  • 打印存储在当前节点内的数据。
  • curr = curr->上一个

循环双向链表插入

有 3 种不同的插入情况。

在循环双向链表的开头插入元素

• 用给定的数据创建一个节点 temp。
• 将 temp->next 设置为 head，将 temp->prev 设置为 tail，以便在 head 和 tail 之间插入 temp。
• 将 tail->next 和 head->prev 设置为 temp 以完成插入。
• 将 head 设置为 temp，以将 head 移至新插入的元素。

在循环双向链表的末尾插入一个元素

• 用给定的数据创建一个节点 temp。
• 如果列表为空，则使用给定数据创建节点 temp，并将 temp->prev 和 temp->next 指向其自身，并将其设置为 head 并返回。
• 执行开始时要插入的步骤，最后一步除外。

在循环双向链表的中间插入元素

令 X 为要在其后插入元素的节点的值。

• 用给定的数据创建一个节点 temp。
• 初始化指向 head 的指针 curr。
• 迭代直到找到带有数据 =X 的节点。将其下一个节点存储为下一个。
• 将 curr->next 设置为 temp。
• 将 temp->prev 设置为 curr，将 temp->next 设置为 next。
• 最后，将下一个->上一个设置为温度。

循环双向链表插入过程

1. 在循环双向链表的开头插入元素
2. 在循环双向链表的末尾插入一个元素
3. 在循环双向链表的中间插入元素

循环双向链表遍历和插入实现

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int data;
    Node *next;
    Node *prev;
};
void insertEnd(Node** head, int value)
{
    if (*head == NULL)
    {
        Node* temp = new Node;
        temp->data = value;
        temp->next = temp->prev = temp;
        *head = temp;
        return;
    }
    Node *tail = (*head)->prev;
    Node* temp = new Node;
    temp->data = value;
    temp->next = *head;
    (*head)->prev = temp;
    temp->prev = tail;
    tail->next = temp;
}

void insertBegin(Node** head, int value)
{

    Node *tail = (*head)->prev;

    Node* temp = new Node;
    temp->data = value;
    temp->next = *head;
    temp->prev = tail;


    tail->next = (*head)->prev = temp;

    *head = temp;
}

void insertAfter(Node** head, int value1,
                 int value2)
{
    Node* temp = new Node;
    temp->data = value1;
    Node *curr = *head;
    while (curr->data != value2)
        curr = curr->next;
    Node *next = curr->next;

    curr->next = temp;
    temp->prev = curr;
    temp->next = next;
    next->prev = temp;
}


void printList(Node* head)
{
    Node *curr = head;

    printf("Forward Traversal:");
    while (curr->next != head)
    {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("%d ", curr->data);

    printf("\nBackward Traversal:");
    Node *tail = head->prev;
    curr = tail;
    while (curr->prev != tail)
    {
        printf("%d ", curr->data);
        curr = curr->prev;
    }
    printf("%d ", curr->data);
    cout << "\n";
}

int main()
{
    Node* head = NULL;
    insertEnd(&head, 2);
    insertBegin(&head, 1);
    insertEnd(&head, 4);
    printList(head);
    insertEnd(&head, 5);
    insertAfter(&head, 3, 2);
    printList(head);
    return 0;
}

循环双向链表遍历和插入算法的复杂性

遍历

• 平均情况

要遍历完整的双向链表，我们必须访问每个节点。如果具有 n 个节点，则遍历的平均情况下时间复杂度约为 O(n)。时间复杂度约为 O(n)。

• 最佳情况

最佳情况下的时间复杂度是 O(n)。它与平均情况下的时间复杂度相同。

• 最坏情况

最差的时间复杂度是 O(n)。它与最佳情况下的时间复杂度相同。

遍历算法的空间复杂度为 O(1)，因为除了 curr 指针外不需要其他空间。

插入

• 平均情况

要在 tail 和 head 处插入要插入的元素，最多需要更改 4 个链接，因此时间复杂度为 O(1)。但是要在两者之间插入，我们可能必须移动 n-1 个节点，因此时间复杂度为 O(n)。

• 最佳情况

对于所有 3 情况，最佳情况下的时间复杂度为 O(1)。

• 最坏情况

对于前两种情况，最坏情况下的时间复杂度为 O(1)，对于第三种情况为 O(n)。它与平均情况下的时间复杂度相同。

对于所有 3 种类型的插入，插入算法的空间复杂度为 O(1)。