迴圈雙向連結串列

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