雙向連結列表

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 雙向連結列表 vs 連結列表
  2. 雙向連結列表遍歷演算法
  3. 雙向連結列表插入
  4. 雙向連結列表插入插圖
  5. 雙向連結列表遍歷和插入實現
  6. 雙向連結列表遍歷和插入演算法的複雜性
雙向連結列表

雙向連結列表是線性資料結構。它是定義為節點的物件的集合。但是與連結列表不同,該節點有兩個指標,一個是前一個指標,另一個是下一個指標。就像連結串列節點儲存在記憶體中的隨機位置中,而不是儲存在連續位置中一樣。

雙向連結列表 vs 連結列表

  1. 雙向連結列表允許我們在向前和向後的方向上遍歷連結列表,但這是以 prev 指標為每個節點所需的額外空間為代價的。
  2. 在雙向連結串列中插入元素非常容易,因為我們不必維護多個指標或遍歷連結串列來查詢先前的指標,但是與連結串列相比,我們必須修改更多的指標。

雙向連結列表遍歷演算法

前進方向

head 成為連結列表的第一個節點。

  • 初始化 curr,指向連結列表的 head 節點。
  • 雖然 curr 尚未到達列表的末尾,即 curr!=NULL,但請執行以下操作:
    • 列印儲存在當前節點內的資料。
    • curr=curr->next;
    • 如果是最後一個節點,則儲存為 tail,以方便向後遍歷。

同樣,我們可以通過從 tail 開始並將 curr 更改為 curr->prev 來進行向後遍歷。

反方向

tail 為連結串列的最後一個節點。

  • 初始化 curr,指向連結列表的 tail 節點。
  • 雖然 curr 尚未到達列表的開頭,即 curr!=NULL,但請執行以下操作:
    • 列印儲存在當前節點內的資料。
    • curr = curr->上一個

雙向連結列表插入

雙向連結列表在插入元素時有 4 種情況,就像連結串列一樣。

將節點插入 DLL push() 的開頭

  • 使用資料 xprev 建立為 NULL 的新節點 temp
  • temp->next 設定為 head,將 head->prev 設定為 temp,以在 head 之前插入 temp
  • temp 設定為連結列表的開頭。

Append()DLL 末尾插入節點

  • 建立一個新節點 temp,其資料為 x,並且其 prevNULL
  • 初始化指向 headtail
  • 如果連結列表為空,則將 temp 設定為連結列表的 head,然後返回。
  • 否則,迭代連結列表的末尾,使 tail->next!=NULL,以便你到達最後一個元素
  • tail->next 設定為 temp,將 temp->prev 設定為 tail

在給定節點 insertBefore() 之前插入節點

  • 如果 next==NULL,則返回;
  • 用資料 x 建立一個新節點 curr
  • curr->prev 設定為 next->prev,以在 next 之前新增一個新節點,將 next->prev 設定為 curr,以建立後向連結。
  • curr->next 設定為 next,最後檢查 curr->prev 是否為 NULL
  • 如果不是 NULL,則將 curr->prev->next 設定為 curr 以完成插入,否則 curr 是連結列表的第一個節點。將 head 設定為 curr

在給定節點 insertAfter() 之後插入節點

  • 如果 prev==NULL,則返回;
  • 用資料 x 建立一個新節點 curr
  • curr->next 設定為 prev->next,以在 prev 之後新增一個新節點,並將 prev->next 設定為 curr,以建立前向連結。
  • curr->prev 設定為 prev,最後檢查 curr->next 是否為 NULL。如果不是 NULL,則將 curr->next->prev 設定為 curr 以完成插入。

雙向連結列表插入插圖

將節點插入 DLL push() 的開頭

Append()DLL 末尾插入節點

在給定節點 insertBefore() 之前插入節點

在給定節點 insertAfter() 之後插入節點

雙向連結列表遍歷和插入實現

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node* prev;
};

void push(Node** head, int x)
{
    Node* curr = new Node();
    curr->data = x;
    curr->next = (*head);
    curr->prev = NULL;
    if ((*head) != NULL)
        (*head)->prev = curr;
    (*head) = curr;
}
void insertAfter(Node* prev, int x)
{
    if (prev == NULL)
    {
        cout << "the given previous node cannot be NULL";
        return;
    }

    Node* curr = new Node();
    curr->data = x;
    curr->next = prev->next;
    prev->next = curr;
    curr->prev = prev;
    if (curr->next != NULL)
        curr->next->prev = curr;
}

void insertBefore(struct Node** head, struct Node* next, int x)
{    if (next == NULL) {
        return;
    }

    Node* curr = new Node();
    curr->data = x;
    curr->prev = next->prev;
    next->prev = curr;
    curr->next = next;
    if (curr->prev != NULL)
        curr->prev->next = curr;
    else
        (*head) = curr;
}

void append(Node** head, int x)
{
    Node* curr = new Node();
    Node* tail = *head;
    curr->data = x;
    curr->next = NULL;
    if (*head == NULL)
    {
        curr->prev = NULL;
        *head = curr;
        return;
    }
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = curr;
    curr->prev = tail;
    return;
}

void printList(Node* node)
{
    Node* tail = NULL;
    cout << "Forward Traversal:";
    while (node != NULL)
    {
        cout << " " << node->data << " ";
        tail = node;
        node = node->next;
    }

    cout << "\nReverse Traversal:";
    while (tail != NULL)
    {
        cout << " " << tail->data << " ";
        tail = tail->prev;
    }
    cout << "\n";
}

int main()
{

    Node* head = NULL;
    append(&head, 6);
    push(&head, 7);
    push(&head, 1);
    append(&head, 4);
    printList(head);
    insertAfter(head->next, 8);
    insertBefore(&head, head->next->next, 3);
    printList(head);
    return 0;
}

雙向連結列表遍歷和插入演算法的複雜性

遍歷

時間複雜度

  • 平均情況

要遍歷完整的雙向連結串列,我們必須訪問每個節點。因此,如果它具有 n 個節點,則遍歷的平均情況下時間複雜度約為 O(n)。時間複雜度約為 O(n)

  • 最佳情況

最佳情況下的時間複雜度是 O(n)。它與平均情況下的時間複雜度相同。

  • 最壞情況

最差的時間複雜度是 O(n)。它與最佳情況下的時間複雜度相同。

空間複雜度

遍歷演算法的空間複雜度為 O(1),因為除 curr 指標外不需要其他空間。

插入方式

時間複雜度

  • 平均情況

在所有 4 情況下插入一個元素最多需要 4 連結更改,因此插入的時間複雜度為 O(1)

  • 最佳情況

最佳情況下的時間複雜度是 O(1)。它與平均情況下的時間複雜度相同。

  • 最壞情況

最壞情況下的時間複雜度是 O(1)。它與最佳情況下的時間複雜度相同。

空間複雜度

對於所有 4 種插入方式,插入演算法的空間複雜度為 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