資料結構與演算法：List 連結串列

• List：相較於陣列須要以連續記憶體空間儲存資料，List 允許以不連續之記憶體空間儲存連續之資料。

List interface：

interface List{
    private first: Node;
	private size: number;
    
    public insertFirst(value: any);
    public insertLast(value: any);
    public delete(index: number);
    public deleteFirst(index: number);
    public deleteLast(index: number);
	public reverse();
    public concatenate(list: LinkedList);
    public copy();
    public get(index: number);
    public getSize();
}

1. Singly Linked List

• 每個 Node中有一個 next 屬性指向下一個 Node
• 優點：
  • insert與delete 方便與快速
  • 不須要連續的記憶體空間
• 缺點：
  • 須要多儲存下一個Node資訊
  • 取出第 N 筆資料速度比陣列慢，需要從 first/ head 開始逐一往下尋找，需要 O(N)
  • 反向遍歷 List 不容易實做

class Node{
	value: any;
    next: Node;
}

value: 儲存內容

next: 指向下一個Node

新增FAT於 BAT 節點後：

刪除BAT節點：

合併兩個LIST：

2. Doubly Linked List

• 相較於 Singly Linked List，Node 內多了一個 prev 紀錄前一個Node資訊

• 優點：
  • 可解決 Singly Linked List所遇到的問題：
    • 在刪除第 n 筆 Node 前必須先找到第 n-1 筆 Node
    • 如果Singly Linked List 中有一個 next 出了問題（未正確指向下一個Node），則無法恢復資料
  • 不須要連續的記憶體空間
• 缺點：
  • 需要較多空間儲存前一節點資訊

class Node{
    private prev: Node;
    private next: Node;
    private value: any;
}

prev：前一Node

next：下一個Node

value：儲存的值

新增MAT node：

刪除FAT node：

僅需要改變 CAT的next 與 HAT的prev 指向位置即可

3. Circular Linked List

List的一種變形，將 List 最後一個 Node 的next 指向第一個 Node，形成一個環狀 List。

Singly Circular Linked List：

Doubly Circular Linked List：

• 優點：
  • 從first到last只需要 O(1)
  • 容易做到反向查詢
  • 如果要遍歷整個List，任何節點都可以作為起始Node
• 缺點：
  • 需要多一些空間儲存前一Node資訊

4. Available List

為List 一種改良機制，當List 執行delete Node時，不將被刪除的Node刪除，反而是將被刪除的List加入一個 available list中，當需要新增Node時，第一時間先檢查available list中有沒有可用的 Node，有的話從available list中取出Node使用，沒有的話才重新 new一個 Node，如此一來可以減少 Node 執行 new 的次數（效能提升）。

刪除FAT Node：

刪除FAT node後，會將FAT新增至Availabel List中

新增Node：

新增時，會優先參考Available list中是否有可用的node，如果有則先從Available list中取出使用，可減少執行 new物件的次數。

5. 複雜度比較

如果知道要新增與刪除 Node，如head或 tail，則時間複雜度為 O(1)，若不知道的情況，則必須先搜尋才可新增刪除，這時需要將搜尋的時間複雜度算入。

6. List 實際應用

1. Windows 圖片檢視器
2. 音樂播放器清單
3. Block Chain