什麼是連結串列#
連結串列跟一維陣列一樣，都是用來儲存資料的工具。下圖為一個連結串列的範例。
圖中可以看到一個連結串列會有一個起點 (head)，起點會有一個箭頭 (next) 連結到下一個點，以此類推直到連結串列的尾端。
連結串列也可以是雙向的，如下圖。
連結串列與一維陣列的比較#
| 連結串列 | 一維陣列 | |
|---|---|---|
| 記憶體分布 | 可不連續 | 連續 |
| 記憶體大小 | 動態調整 | 固定不變 |
| 長度相同時的記憶體 | 較大(要儲存下一個元素的位置) | 較小(下一個元素就在自己的下一個位置) |
| 求第 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
看完單向連結串列的實作後，也可以思考雙向的連結串鍊要怎麼實作喔 !
