連結串列
連結串列是線性資料結構。它是定義為節點的物件的集合。但是在連結列表中,節點儲存在記憶體中的隨機位置中,而不儲存在連續位置中。
連結串列的一個節點包括:
-
資料項。
-
下一個節點的地址。
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 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