連結串列

什麼是連結串列

連結串列跟一維陣列一樣，都是用來儲存資料的工具。下圖為一個連結串列的範例。

圖中可以看到一個連結串列會有一個起點 (head)，起點會有一個箭頭 (next) 連結到下一個點，以此類推直到連結串列的尾端。

連結串列也可以是雙向的，如下圖。

連結串列與一維陣列的比較

	連結串列	一維陣列
記憶體分布	可不連續	連續
記憶體大小	動態調整	固定不變
長度相同時的記憶體	較大<br>(要儲存下一個元素的位置)	較小<br>(下一個元素就在自己的下一個位置)
求第 n 個元素的時間	O(n)	O(1)
插入或刪除元素的時間	O(1)	O(n)

連結串列的實作方式

實作連結串列的方式主要有兩種，指標和偽指標。在競賽或檢定中通常會使用偽指標來實作連結串列，因為偽指標寫起來比較簡單不易出錯。

以單向的連結串列為例，會需要創建兩個陣列，第一個紀錄數值，第二個紀錄每個點的下一個元素是誰。

int arr[5] = {0, 1, 2, 3, 4};
int next[5];
int head = 1;
next[1] = 2;
next[2] = 4;
next[4] = 3;
next[3] = -1; // 連結串列的尾端
// 連結串列會長這樣  1 -> 2 -> 4 -> 3
int now = head;  // now = 1
now = next[now]; // now = 2
now = next[now]; // now = 4
now = next[now]; // now = 3

看完單向連結串列的實作後，也可以思考雙向的連結串鍊要怎麼實作喔 !