指標

列表是資料結構的一種，這類結構的數據排成一直線，便於追加或刪除，但存取數據卻很費時。

每個「數據」和一個「指標」配對，指向下一個數據在記憶體中的位址 其中，Red 是最後的數據，所以其指標沒有指向任何位址

列表中，數據不需要連續儲存於記憶體中，一般分散於各個記憶體區塊

順序存取 (sequential access)

由於數據被分散儲存，所以只能從頭依序跟著指標存取各數據
如上圖動畫：要存取 Red，必須透過 Blue 取得 Yellow 後，才能取得 Red

增加數據

只要把追加位址前後的指標轉向即可，例如想在 Blue 與 Yellow 之間增加 Green 僅需將 Blue 指標指向 Green，再把 Green 的指標指向 Yellow 即可

p.s 記得，所有數據在記憶體區塊中都可不必連續儲存

刪除數據

同樣將指標轉向即可，例如想刪除 Yellow，僅需將 Green 的指標指向 Red Yellow 區塊雖仍存在記憶體中，但是已無法被存取。

p.s 若要重複使用這個記憶體區塊，僅需覆寫即可。

執行時間討論 (以 大O符號 表示)

1. 使用列表內的數據的執行時間
   假設列表中的數據有 n 個，存取最後一個數據必須從頭開始，因此為 O(n)
2. 新增數據
   僅需改變 2 個指標指向，與列表中 n 個數據無關，因此為常數時間 O(1)
   前提是已知數據新增位置，否則需考慮從數據查找的執行時間
3. 刪除數據
   同樣僅需耗費常數時間 O(1)

其他列表

• 環狀列表 / 循環列表 (Circular List)
  將最後一個數據的指標指向第一個數據，就能形成環狀。此列表沒有頭尾區分，可用來限制列表內的數據數量。
• 雙向列表 (Bidirectional List)
  當每個數據帶 2 個指標，分別指向前後數據。此列表一樣沒有頭尾區分，且可從另一端來存取。 此列表的缺點為必須增加記憶體使用量，且新增或刪除數據時，要變更方向的指標數也變多了。