循环双向链表

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 循环双向链表遍历
  2. 循环双向链表插入
  3. 循环双向链表插入插图
  4. 循环双向链表遍历和插入实现
  5. 循环双向链表遍历和插入算法的复杂性
循环双向链表

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

循环双向链表遍历

我们只需检查迭代中的下一个节点不是 head 的条件,然后遍历循环双向链表,然后根据向前/向后将 temptemp->nexttemp->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,以便在 headtail 之间插入 temp
  • tail->nexthead->prev 设置为 temp 以完成插入。
  • head 设置为 temp,以将 head 移至新插入的元素。

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

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

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

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

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

循环双向链表插入插图

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

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

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

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

#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 指针外不需要其他空间。

插入

时间复杂度

  • 平均情况

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

  • 最佳情况

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

  • 最坏情况

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

空间复杂度

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

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Data Structure