連結串列

1. 連結列表與陣列的比較
2. 連結串列遍歷演算法
3. 連結串列遍歷圖解
4. 連結串列遍歷實現
5. 連結串列遍歷演算法複雜度

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

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

• 資料項。

• 下一個節點的地址。

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

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

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

連結列表與陣列的比較

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

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

連結串列遍歷演算法

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

連結串列遍歷圖解

連結串列遍歷實現

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