# Data Structure / Singly Linked List
## 1. 基本概念
單向鏈結串列由一系列節點組成，**每個節點包含數據和指向下一個節點的指標。**
### 1.1 節點結構
一個基本的節點結構如下（等等會解釋不用擔心）：
```java=
class IntNode {
public int info;
public IntNode next;
public IntNode(int i) {
this(i， null);
}
public IntNode(int i， IntNode n) {
info = i;
next = n;
}
}
```
### 1.2 節點結構 - 逐行解釋
樓上看不懂沒關係，我一開始也看不懂，所以我們慢慢講。
程式碼首先定義了一個名為 `IntNode` 的類別，主要用於實現鏈表（Linked List）資料結構中的**節點**。這個節點包含兩個主要部分：存放資料的變數 + 指向下一個節點的引用。
#### 1.2.1 類別定義
```java
class IntNode {
```
這行程式碼宣告了一個名為 `IntNode` 的類別，這個類別通常用於鏈表中的節點表示。鏈表是一種資料結構，其中每個節點都包含資料（`info`）以及指向下一個節點的引用（`next`）。
#### 1.2.2 變數宣告
```java
public int info;
```
這行宣告了一個公開的整數變數 `info`，它用來存放節點中的資料。由於它是 `public` 的，所以該變數可以在其他類別中直接存取。
```java
public IntNode next;
```
這行宣告了一個公開的 `IntNode` 型別變數 `next`，它用來指向下一個節點。如果 `next` 為 `null`，那麼當前節點就是鏈表的末尾節點。
#### 1.2.3 建構子：單一參數版本
```java
public IntNode(int i) {
this(i, null);
}
```
這段程式碼定義了一個只有一個參數的建構子，參數 `i` 用來初始化 `info`。同時，這個建構子呼叫了另一個建構子 `IntNode(int i, IntNode n)`，並且將第二個參數設為 `null`，表示這個節點目前沒有指向任何下一個節點。
`this(i, null);` 的作用是**呼叫另一個帶有兩個參數的建構子** `IntNode(int i, IntNode n)`，從而簡化初始化的邏輯。
#### 1.2.4 建構子：完整版本
```java
public IntNode(int i, IntNode n) {
info = i;
next = n;
}
```
來了這就是 Overloading，這個建構子接受兩個參數：`i` 和 `n`。`i` 是節點的資料，`n` 是指向下一個節點的引用，所以它允許在創建節點時同時設定資料和下一個節點的引用。
#### `this(i, null)` 的作用
`this(i, null)` 是 Java 中用來呼叫同一個類別中其他建構子的語法。在這裡，`this(i, null)` 會呼叫另一個建構子 `IntNode(int i, IntNode n)`，並將第二個參數設為 `null`，表示這個節點暫時不指向任何下一個節點。
具體來說，當使用簡單建構子 `IntNode(int i)` 時，會透過 `this(i, null)` 呼叫完整建構子 `IntNode(int i, IntNode n)`，這樣就可以一次性設定 `info` 和 `next`，以達到避免重複程式碼、保持程式碼一致性和提高可讀性等優點。
### 1.3 SLL 結構
一個基本的鏈結串列結構如下（等等會解釋不用擔心）：
```java=
class IntSLList {
private IntNode head, tail;
public IntSLList() {
head = tail = null;
}
}
```
### 1.4 SLL 結構 - 逐行解釋
樓上看不懂沒關係，我一開始也看不懂，所以我們慢慢講。
程式碼首先定義了一個名為 `IntSLList` 的類別，主要用於實現鏈表（Linked List）的主體。它包括兩個變數：`head` 用來指向鏈表的第一個節點 + `tail` 指向最後一個節點。建構子初始化時，鏈表為空，`head` 和 `tail` 都設為 `null`。
#### 1.4.1 類別定義
```java
class IntSLList {
```
這是宣告一個名為 `IntSLList` 的類別，用來表示一個單向鏈表。
#### 1.4.2 變數宣告
```java
private IntNode head, tail;
```
這行定義了兩個私有成員變數 `head` 和 `tail`。這些變數是鏈表的頭和尾節點。它們的類型是 `IntNode`，代表鏈表中的節點。
- `head` 指向鏈表的第一個節點。
- `tail` 指向鏈表的最後一個節點。
- 因為這些變數是 `private`，所以它們只能在這個類別內部使用，外部無法直接訪問。
#### 1.4.3 建構子
```java
public IntSLList() {
head = tail = null;
}
```
- `public IntSLList()`：這是一個公共的建構子，當創建 `IntSLList` 對象時，這個建構子會被調用。
- `head = tail = null;`：這行將 `head` 和 `tail` 初始化為 `null`，表示這個鏈表目前是空的，還沒有任何節點。
## 2. 基本操作詳解
### 2.0 Helpers 輔助函數
```java=
public boolean isEmpty() {
return head == null;
}
public void printList() {
if (head == null) {
System.out.println("The list is empty");
return;
}
IntNode temp = head;
while (true) {
if (temp == null) {
break;
}
System.out.print(temp.info + " ");
temp = temp.next;
}
}
```
### 2.1 插入操作
插入操作是鏈結串列最基本且最常用的操作之一。根據插入位置的不同，我們有三種主要的插入方式：頭部插入、尾部插入和中間插入。
#### 2.1.1 在頭部插入
在頭部插入是最簡單的插入操作，時間複雜度為 O(1)。
```java=
public void addToHead(int el) {
head = new IntNode(el, head);
if (tail == null) // 如果原本串列為空
tail = head;
}
```
這個操作的步驟如下：
1. 創建一個新節點，其數據為 el，next 指向當前的 head。
2. 將 head 更新為這個新節點。
3. 如果原本串列為空（tail 為 null），則將 tail 也指向這個新節點。
#### 2.1.2 在尾部插入
在尾部插入的時間複雜度也是 O(1)，因為我們維護了一個 tail 指標。
```java=
public void addToTail(int el) {
if (!isEmpty()) {
tail.next = new IntNode(el);
tail = tail.next;
} else
head = tail = new IntNode(el);
}
```
這個操作的步驟如下：
1. 如果串列不為空，創建一個新節點並將其接在 tail 後面，然後更新 tail。
2. 如果串列為空，創建一個新節點並將 head 和 tail 都指向它。
#### 2.1.3 在中間插入
在中間插入需要先找到插入位置，因此時間複雜度為 O(n)。
```java=
public void insertAfter(int key, int el) {
IntNode current = head;
while (current != null && current.info != key) {
current = current.next;
}
if (current != null) {
current.next = new IntNode(el, current.next);
if (current == tail) {
tail = current.next;
}
}
}
```
這個操作的步驟如下：
1. 遍歷串列找到包含 key 的節點。
2. 如果找到了，在該節點後插入新節點。
3. 如果插入位置是尾部，需要更新 tail。
### 2.2 刪除操作
刪除操作也有三種主要情況：刪除頭部、刪除尾部和刪除中間節點。
#### 2.2.1 刪除頭部節點
刪除頭部節點的時間複雜度為 O(1)。
```java=
public int deleteFromHead() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
int el = head.info;
if (head == tail) {
head = tail = null;
} else {
head = head.next;
}
return el;
}
```
這個操作的步驟如下：
1. 檢查串列是否為空，如果為空則拋出異常。
2. 保存頭部節點的數據。
3. 如果串列只有一個節點，將 head 和 tail 都設為 null。
4. 否則，將 head 移到下一個節點。
5. 返回刪除的數據。
#### 2.2.2 刪除尾部節點
刪除尾部節點的時間複雜度為 O(n)，因為我們需要遍歷到倒數第二個節點。
```java=
public int deleteFromTail() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
int el = tail.info;
if (head == tail) {
head = tail = null;
} else {
IntNode temp = head;
while (temp.next != tail) {
temp = temp.next;
}
tail = temp;
tail.next = null;
}
return el;
}
```
這個操作的步驟如下：
1. 檢查串列是否為空，如果為空則拋出異常。
2. 保存尾部節點的數據。
3. 如果串列只有一個節點，將 head 和 tail 都設為 null。
4. 否則，遍歷到倒數第二個節點，將其設為新的 tail，並將其 next 設為 null。
5. 返回刪除的數據。
#### 2.2.3 刪除特定元素
刪除特定元素的時間複雜度為 O(n)，因為我們需要遍歷串列找到該元素。
```java=
public boolean delete(int el) {
if (isEmpty()) {
return false;
}
if (head.info == el) {
deleteFromHead();
return true;
}
IntNode pred = head, temp = head.next;
while (temp != null && temp.info != el) {
pred = pred.next;
temp = temp.next;
}
if (temp != null) {
pred.next = temp.next;
if (temp == tail) {
tail = pred;
}
return true;
}
return false;
}
```
這個操作的步驟如下：
1. 檢查串列是否為空，如果為空則返回 false。
2. 如果要刪除的是頭部節點，調用 deleteFromHead() 方法。
3. 否則，遍歷串列找到要刪除的節點及其前驅。
4. 如果找到了要刪除的節點，將其前驅的 next 指向要刪除節點的 next。
5. 如果刪除的是尾部節點，更新 tail。
6. 返回是否成功刪除。
### 2.3 完整程式碼 Demo
```java=
import java.util.*;
class IntNode {
public int info;
public IntNode next;
public IntNode(int info) {
this(info, null);
}
public IntNode(int info, IntNode next) {
this.info = info;
this.next = next;
}
}
class IntSLList {
private IntNode head, tail;
// constructor
public IntSLList() {
head = tail = null;
}
// helpers
public boolean isEmpty() {
return head == null;
}
public void printList() {
if (head == null) {
System.out.println("The list is empty");
return;
}
IntNode temp = head;
while (true) {
if (temp == null) {
break;
}
System.out.print(temp.info + " ");
temp = temp.next;
}
}
// ADD Methods
public void addToHead(int el) {
head = new IntNode(el, head);
if (tail == null)
tail = head;
}
public void addToTail(int el) {
if (!isEmpty()) {
tail.next = new IntNode(el);
tail = tail.next;
} else
head = tail = new IntNode(el);
}
public void insertAfter(int key, int el) {
IntNode current = head;
while (current != null && current.info != key) {
current = current.next;
}
if (current != null) {
current.next = new IntNode(el, current.next);
if (current == tail) {
tail = current.next;
}
}
}
// DELETE Methods
public int deleteFromHead() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
int el = head.info;
if (head == tail) {
head = tail = null;
} else {
head = head.next;
}
return el;
}
public int deleteFromTail() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
int el = tail.info;
if (head == tail) {
head = tail = null;
} else {
IntNode temp = head;
while (temp.next != tail) {
temp = temp.next;
}
tail = temp;
tail.next = null;
}
return el;
}
public boolean delete(int el) {
if (isEmpty()) {
return false;
}
if (head.info == el) {
deleteFromHead();
return true;
}
IntNode pred = head, temp = head.next;
while (temp != null && temp.info != el) {
pred = pred.next;
temp = temp.next;
}
if (temp != null) {
pred.next = temp.next;
if (temp == tail) {
tail = pred;
}
return true;
}
return false;
}
}
public class DS {
public static void main(String[] args) {
IntSLList L = new IntSLList();
L.addToHead(0);
L.addToTail(5);
L.insertAfter(0, 3);
L.printList();
System.out.println();
L.deleteFromHead();
L.deleteFromTail();
L.delete(3);
L.printList();
}
}
```
#### Output:
:::success
**0 3 5
The list is empty**
:::
## 3. 進階操作詳解
### 3.1 反轉鏈結串列
反轉鏈結串列是一個常見的面試題目，也是一個很好的練習題。這個操作的時間複雜度為 O(n)，空間複雜度為 O(1)。
```java=
public void reverse() {
if (head == null || head.next == null) {
return; // 空串列或只有一個節點，無需反轉
}
IntNode prev = null;
IntNode current = head;
tail = current; // 原來的頭變成尾
while (current != null) {
IntNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
head = prev; // 原來的尾變成頭
}
```
這個操作的步驟如下：
1. 如果串列為空或只有一個節點，無需反轉，直接返回。
2. 初始化三個指標：prev（指向前一個節點）、current（指向當前節點）和 nextTemp（臨時保存下一個節點）。
3. 將原來的頭節點設為新的尾節點。
4. 遍歷串列，對每個節點：
- 保存下一個節點
- 將當前節點的 next 指向前一個節點
- 將 prev 和 current 都向前移動一步
5. 遍歷結束後，將 head 指向新的頭節點（原來的尾節點）。
### 3.2 檢測循環
檢測鏈結串列中是否存在循環是另一個常見的問題。我們可以使用 Floyd 的龜兔算法（又稱為快慢指標法）來解決這個問題。這個算法的時間複雜度為 O(n)，空間複雜度為 O(1)。
```java=
public boolean hasCycle() {
if (head == null || head.next == null) {
return false; // 空串列或只有一個節點，不可能有循環
}
IntNode slow = head;
IntNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false; // 到達串列尾部，沒有循環
}
slow = slow.next; // 慢指標每次移動一步
fast = fast.next.next; // 快指標每次移動兩步
}
return true; // 快慢指標相遇，存在循環
}
```
這個算法的原理如下：
1. 使用兩個指標，一個慢指標（每次移動一步）和一個快指標（每次移動兩步）。
2. 如果存在循環，快指標最終會追上慢指標，兩者相遇。
3. 如果不存在循環，快指標會先到達串列尾部。
### 3.3 找到中間節點
找到鏈結串列的中間節點是另一個有趣的問題。我們可以繼續使用快慢指標法來解決這個問題，時間複雜度為 O(n)，空間複雜度為 O(1)。
```java=
public IntNode findMiddle() {
if (head == null) {
return null;
}
IntNode slow = head;
IntNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // slow 指向中間節點
}
```
這個算法的原理如下：
1. 使用兩個指標，慢指標每次移動一步，快指標每次移動兩步。
2. 當快指標到達串列尾部時，慢指標恰好在中間位置。
3. 如果節點數量為偶數，這個方法會返回兩個中間節點的第二個。
### 3.4 合併兩個有序鏈結串列
合併兩個已排序的鏈結串列是另一個常見的操作。這個操作的時間複雜度為 O(n+m)，其中 n 和 m 是兩個串列的長度。
```java=
public static IntNode mergeSortedLists(IntNode l1, IntNode l2) {
IntNode dummy = new IntNode(0); // 虛擬頭節點
IntNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.info <= l2.info) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
// 將剩餘的節點接上
if (l1 != null) {
current.next = l1;
}
if (l2 != null) {
current.next = l2;
}
return dummy.next; // 返回合併後的頭節點
}
```
這個算法的步驟如下：
1. 創建一個虛擬頭節點，簡化邊界情況的處理。
2. 比較兩個串列的當前節點，將較小的節點加入到結果串列中。
3. 重複步驟 2，直到其中一個串列遍歷完畢。
4. 將剩餘串列的節點直接接到結果串列的尾部。
5. 返回虛擬頭節點的下一個節點，即為合併後串列的真正頭節點。
這些進階操作不僅在面試中常見，也在實際編程中經常用到。掌握這些操作可以幫助我們更好地理解和運用鏈結串列這種數據結構。
## 4. 應用實例
### 4.1 長整數相加
使用鏈結串列來實現兩個長整數的相加操作：
```java=
public IntSLList addTwoNumbers(IntSLList l1， IntSLList l2) {
IntSLList result = new IntSLList();
IntNode p = l1.head， q = l2.head;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.info ： 0;
int y = (q != null) ? q.info ： 0;
int sum = carry + x + y;
carry = sum / 1000;
result.addToTail(sum % 1000);
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
result.addToTail(carry);
}
return result;
}
```
## 5. 效能考量
- 插入和刪除操作： O(1) 時間複雜度（如果知道節點位置）
- 搜尋操作： O(n) 時間複雜度
- 空間複雜度： O(n)
單向鏈結串列在需要頻繁插入和刪除操作，但不需要隨機訪問的場景下表現優異。
## 6. 注意事項
1. 要處理邊界情況，如空串列或只有一個節點的情況。
2. 在刪除節點時，要特別注意更新 head 和 tail 指標。
3. 使用鏈結串列時，要小心避免產生循環，除非是刻意為之。
Sign in with Wallet
Connect another wallet