連結串列

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 連結列表與陣列的比較
  2. 連結串列遍歷演算法
  3. 連結串列遍歷圖解
  4. 連結串列遍歷實現
  5. 連結串列遍歷演算法複雜度
連結串列

連結串列是線性資料結構。它是定義為節點的物件的集合。但是在連結列表中,節點儲存在記憶體中的隨機位置中,而不儲存在連續位置中。

連結串列

連結串列的一個節點包括:

  • 資料項。

  • 下一個節點的地址。

class Node
{
    int data;
    Node *next;
};

節點的這種表示形式用於建立列表中的每個節點。資料欄位儲存元素,而*next 是儲存下一個節點地址的指標。

第一個節點的地址稱為頭,最後一個節點的地址稱為尾。連結列表中的最後一個節點指向 NULL。因此,當列表為空時,頭節點指向 NULL 節點。連結列表不需要事先宣告大小,並且可以動態增加大小。在連結串列中插入和刪除元素非常容易。我們不需要移動所有要素;僅更改上一個和下一個元素的指標就足夠了。

連結列表與陣列的比較

連結列表比陣列具有自然的優勢,因為我們不必事先分配大量的記憶體,但是由於記憶體不是連續分配的,因此連結列表快取起來也不友好。它們允許在指標的幫助下輕鬆地插入和刪除元素,但由於指標所需的空間,每個節點的儲存空間也要加倍。連結列表也不提供對元素的隨機訪問。因此,很明顯,沒有一個贏家,而且連結串列和陣列都有各自的優缺點。

當我們有一個小列表並且知道我們可能儲存的最大元素數量時,應該使用陣列,而當有一個大列表定期更改時,應該使用連結列表。

連結串列遍歷演算法

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

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

連結串列遍歷圖解

連結串列遍歷

  • 初始化指向 head 節點的指標 curr,資料值等於 2。列印值 2

  • 將指標 curr 移動到下一個節點,數值為 4。列印值 4

  • 將指標 curr 移動到下一個節點,數值為 6。列印數值 6

  • 將指標 curr 移動到下一個節點,數值為 8。列印值 8

  • 將指標 curr 移動到下一個節點,該節點的值等於 NULL。達到 while 迴圈終止條件。因此,我們已經訪問了所有的節點。

連結串列遍歷實現

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

class Node {
public:
    int data;
    Node* next;
    Node(int x) {
        this->data = x;
        this->next = NULL;
    }
};

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    head -> next-> next = new Node(3);
    head -> next-> next-> next = new Node(4);
    head -> next-> next-> next-> next = new Node(5);
    head -> next-> next-> next-> next-> next = new Node(6);
    printList(head);
    return 0;
}

連結串列遍歷演算法複雜度

時間複雜度

  • 平均情況

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

  • 最佳情況

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

  • 最壞情況

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

空間複雜度

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

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

相關文章 - Linked List