# 用Java學資料結構-單向鏈結串列 Singly Linked List

## 介紹與概念

### 單向鏈結串列的定義

單向鏈結串列 (Singly Linked List) 是一種基本的資料結構，由節點 (Node) 組成，每個節點包含資料 (data) 和指向下一個節點的指標 (next)。而第一個節點稱為首節點 (Head)，會指向第二個節點，以此類推，直到最後一個節點稱為尾節點，其指標為空 (null)。


### 和陣列的差異比較

| 特性 | 單向鏈結串列 | 陣列 |
|------|------------|------|
| 記憶體配置 | 動態分配、不連續空間 | 靜態分配、連續空間 |
| 存取元素 | O(n)，需要遍歷 | O(1)，可直接透過索引存取 |
| 插入/刪除 | O(1)，只需調整指標 | O(n)，需要搬移元素 |
| 大小 | 動態可變 | 固定大小 |
| 記憶體使用 | 需額外空間存放指標 | 僅需存放資料本身 |

> O(n) 及 O(1) 分別代表時間複雜度，用來描述演算法在輸入 n 個東西時，所需的時間與 n 之間的關係。就是用來衡量演算法執行效率的一個概念。
> O(1) 代表常數時間，不論輸入的大小，執行時間都是固定的。
> O(n) 代表線性時間，隨著輸入的增加，執行時間也會線性增加。
> 在 n 非常大時，好的演算法設計可以大幅降低時間複雜度，提高效率。
> 實務上，我們只會關注時間複雜度的最高次方項，忽略常數因子和低次方項。

> 動態分配、不連續空間: 在程式執行時，根據需要動態分配記憶體空間，節點在記憶體中的位置不連續。
> 靜態分配、連續空間: 在程式編譯時，就分配好固定大小的記憶體空間，元素在記憶體中的位置是連續的。

## 主要優劣勢

### 單向鏈結串列
- ✅ 插入刪除快速
- ✅ 大小可動態調整
- ❌ 存取速度較慢
- ❌ 需額外記憶體存放指標

### 陣列
- ✅ 隨機存取快速
- ✅ 記憶體使用較有效率
- ❌ 大小固定
- ❌ 插入刪除較慢

## 使用場景與優缺點

### ✅動態大小

單向鏈結串列的大小是動態的，這意味著它可以根據需要增加或減少節點的數量，而不需要預先分配固定大小的記憶體。這使得單向鏈結串列非常適合用於需要動態調整大小的應用場景。

- 實際應用
- 任務隊列：在多線程或多任務環境中，任務隊列需要動態地增加和減少任務。
- 瀏覽器歷史記錄：瀏覽器需要記錄用戶的瀏覽歷史，並根據用戶的瀏覽行為動態調整歷史記錄的數量。

### ✅插入與刪除效率高

- 單向鏈結串列在插入和刪除操作上非常高效，因為這些操作只需要調整指標，而不需要搬移元素。這使得單向鏈結串列在需要頻繁插入和刪除操作的應用場景中非常有用。

- 實際應用
- 動態用戶列表：在社交媒體應用中，用戶列表需要動態地增加和減少用戶。
- 動態資源管理：在操作系統中，資源管理需要動態地分配和釋放資源。

### ❌隨機存取困難

單向鏈結串列的隨機存取效率較低，因為要存取第 n 個元素，需要從頭節點開始遍歷 n 個節點。這使得單向鏈結串列在需要頻繁隨機存取的應用場景中不太適合。

- 更適合使用
- 陣列：在需要頻繁隨機存取的應用場景中，陣列是一個更好的選擇，因為陣列可以通過索引直接存取元素。
- 哈希表：在需要快速查找和存取元素的應用場景中，哈希表是一個更好的選擇，因為哈希表可以通過鍵值快速查找元素。

### ❌額外的記憶體開銷

- 單向鏈結串列需要額外的記憶體來存儲指標，這增加了記憶體的使用量。每個節點都需要存儲一個指向下一個節點的指標，這使得單向鏈結串列在記憶體使用上不如陣列高效。

- 更適合使用
- 陣列：在記憶體使用效率要求較高的應用場景中，陣列是一個更好的選擇，因為陣列只需要存儲元素本身，不需要額外的指標。

## 結構與術語
### 節點 (Node) 的概念

單向鏈結串列是由節點 (Node) 組成的，是指鏈結串列中的基本單元，每個節點包含兩部分：

- 資料 (data)：存放節點的值或資訊。
- 指標 (next)：指向下一個節點的指標。

class Node {
    int data;
    Node next;
}

### 頭節點 (Head) 的角色

首節點 (Head) 是鏈結串列的起始節點，用來指向第一個節點。通常在操作鏈結串列時，需要先訪問首節點，然後根據指標 next 來訪問其他節點。

### 尾節點 (Tail) 的特性

尾節點 (Tail) 是鏈結串列的最後一個節點，其指標 next 為空 (null)，表示鏈結串列的結尾。

## 實作與程式碼範例

### 節點 (Node) 的實作

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

### 單向鏈結串列 (Singly Linked List) 的實作

class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    // 新增節點到頭部
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 新增節點到尾部
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 插入節點到指定位置
    public void insert(int index, int data) {
        if (index < 0) {
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        Node newNode = new Node(data);
        Node current = head;
        for (int i = 0; i < index - 1 && current != null; i++) {
            current = current.next;
        }
        if (current == null) {
            return;
        }
        newNode.next = current.next;
        current.next = newNode;
    }

    // 刪除頭部節點
    public void removeFirst() {
        if (head == null) {
            return;
        }
        head = head.next;
    }

    // 刪除尾部節點
    public void removeLast() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            head = null;
            return;
        }
        Node current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        current.next = null;
    }

    // 刪除指定位置的節點
    public void remove(int index) {
        if (index < 0 || head == null) {
            return;
        }
        if (index == 0) {
            head = head.next;
            return;
        }
        Node current = head;
        for (int i = 0; i < index - 1 && current != null; i++) {
            current = current.next;
        }
        if (current == null || current.next == null) {
            return;
        }
        current.next = current.next.next;
    }

    // 根據值查找節點
    public Node find(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return current;
            }
            current = current.next;
        }
        return null;
    }

    // 根據索引查找節點
    public Node get(int index) {
        Node current = head;
        for (int i = 0; i < index && current != null; i++) {
            current = current.next;
        }
        return current;
    }

    // 修改節點值
    public void set(int index, int data) {
        Node current = get(index);
        if (current != null) {
            current.data = data;
        }
    }

    // 輸出鏈結串列
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

### 測試

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addFirst(3);
        list.addFirst(2);
        list.addFirst(1);
        list.addLast(4);
        list.addLast(5);
        list.insert(2, 10);
        list.removeFirst();
        list.removeLast();
        list.remove(2);
        list.set(1, 20);
        list.printList();
    }
}

<!-- ## 進階操作
### 鏈結串列的反轉 (Reverse a Linked List)
### 找到中間節點 (Find Middle Node)
### 檢測循環 (Detect Cycle in Linked List)
### 合併兩個鏈結串列 (Merge Two Sorted Linked Lists)
### 刪除重複節點 (Remove Duplicates)
## 時間與空間複雜度分析
### 各種操作的時間複雜度 (新增、刪除、搜尋)
### 空間複雜度的考量
## 應用場景與實際案例
### 簡單應用：如實現佇列或堆疊
### 複雜應用：如解析字串、儲存數據流
## 常見問題與陷阱
### NullPointerException 的處理
### 操作空鏈結串列的情境
### 記憶體洩漏的風險
## 與其他資料結構的比較
### 單向鏈結串列 vs 雙向鏈結串列
### 單向鏈結串列 vs 雜湊表 (Hash Table)
## 測試與除錯
### 單元測試策略
### 使用調試工具檢查指標指向
延伸閱讀
雙向鏈結串列 (Doubly Linked List)
循環鏈結串列 (Circular Linked List)
鏈結串列在 Java 集合框架中的應用 -->

## Reference

- [http://notepad.yehyeh.net/Content/DS/CH04/3.php](http://notepad.yehyeh.net/Content/DS/CH04/3.php)