# Data Structure / Doubly Linked List

## 1. 基本概念

雙向鏈表的每個節點包含三個主要部分：
- 數據（data）
- 指向前一個節點的指標（prev）
- 指向下一個節點的指標（next）

**`prev` 指標的有無，就是DLL與SLL的主要差別。**

---

**雙向鏈結在實際應用中很有用ㄛ，例如：**

- 瀏覽器的歷史記錄（前進 / 後退功能）
- 音樂播放器的播放清單
- 文字編輯器中的撤銷 / 重做功能
- 快取系統中的 LRU（最近最少使用）演算法

### 1.1 節點結構

基本的節點類定義如下（等等會解釋不用擔心）：

class IntNode {
    int info;
    IntNode next = null, prev = null;
    
    IntNode() { }
    IntNode(int info) { this.info = info; }
    IntNode(int info, IntNode next, IntNode prev) {
        this.info = info;
        this.next = next;
        this.prev = prev;
    }
}

### 1.2 節點結構 - 逐行解釋

#### 1.2.1 類別定義

class IntNode {

這行程式碼宣告了一個名為 `IntNode` 的類別，用來表示雙向鏈結串列中的節點。雙向鏈結串列是一種資料結構，節點包含資料（`info`）、指向前一個節點的變數（`prev`）、以及指向下一個節點的變數（`next`）。

#### 1.2.2 變數宣告

    int info;

這行宣告一個整數變數 `info`，用來存放節點的資料。預設的存取控制是僅能在同一個類別或套件中使用。

    IntNode next = null, prev = null;

這行宣告兩個變數 `next` 和 `prev`，它們的型別是 `IntNode`，分別用來指向下一個節點和前一個節點。這兩個變數的初始值為 `null`，表示目前節點不連接到其他節點。

#### 1.2.3 建構子：無參數版本

    IntNode() { }

這是類別的無參數建構子，當你建立一個節點物件時，如果不傳入任何參數，就會使用這個建構子，它不進行任何初始化操作。

#### 1.2.4 建構子：單參數版本

    IntNode(int el) { 
        info = el; 
    }

這個建構子接受一個參數 `el`，並將它賦值給節點的 `info` 變數，用來初始化節點的資料。此時，`next` 和 `prev` 的值仍然是 `null`。

#### 1.2.5 建構子：完整版本

    IntNode(int info, IntNode next, IntNode prev) {
        this.info = info;
        this.next = next;
        this.prev = prev;
    }

這個建構子接受三個參數：
- `info`：用來初始化節點的資料，賦值給 `this.info`，即當前物件的 `info` 變數。
- `next`：下一個節點，賦值給 `this.next`，即當前物件的 `next` 變數。
- `prev`：前一個節點，賦值給 `this.prev`，即當前物件的 `prev` 變數。

### 1.3 DLL 結構

雙向鏈表類包含指向頭節點和尾節點的指標：

class IntDLList {
    private IntNode head, tail;
    
    public IntDLList() {
        head = tail = null;
    }
}

**（逐行解釋就不再寫ㄌ，[點我回到SLL複習](https://hackmd.io/Fyn8LvpQTH-Bu95CJD4rYQ#14-SLL-%E7%B5%90%E6%A7%8B---%E9%80%90%E8%A1%8C%E8%A7%A3%E9%87%8B)）**

## 2. 基本操作詳解

### 2.0 Helpers 輔助函數

public boolean isEmpty() { // 檢查鏈表是否為空
    return head == null;
}

public void setToNull() { // 將鏈表設為空
    head = tail = null;
}

public int firstEl() { // 獲取頭節點資料
    if (!isEmpty()) {
        return head.info;
    } else {
        return 0; // 或拋出異常
    }
}

### 2.1 插入操作

#### 2.1.1 在頭部插入

在頭部插入是最簡單的插入操作，時間複雜度為 O(1)。

public void addToHead(int el) {
    if (!isEmpty()) {
        head = new IntNode(el, head, null);
        head.next.prev = head;
    } else {
        head = tail = new IntNode(el);
    }
}

這個操作的步驟如下：
1. 如果鏈表不為空，建立一個新的節點 `IntNode`，將新節點的 `next` 設為當前的 `head`，並將新節點設為新的 `head`。隨後，將原本的 `head` 節點的 `prev` 設為新節點，建立雙向鏈結。
2. 如果鏈表為空，則直接將 `head` 和 `tail` 都指向新建立的節點。

#### 2.1.2 在尾部插入

在尾部插入的時間複雜度也是 O(1)，因為我們維護了一個 tail 指標。

public void addToTail(int el) {
    if (!isEmpty()) {
        tail = new IntNode(el, null, tail);
        tail.prev.next = tail;
    } else {
        head = tail = new IntNode(el);
    }
}

這個操作的步驟如下：
1. 如果鏈表不為空，建立一個新節點 `IntNode`，將新節點的 `prev` 設為當前的 `tail`，並將新節點設為新的 `tail`。隨後，將原本的 `tail` 節點的 `next` 設為新節點，完成雙向鏈結。
2. 如果鏈表為空，則將 `head` 和 `tail` 都指向新建立的節點。

#### 2.1.3 在中間插入

在中間插入需要先找到插入位置，因此時間複雜度為 O(n)。

public void insertAfter(int el, int afterEl) {
    IntNode tmp = head;
    while (tmp != null && tmp.info != afterEl) {
        tmp = tmp.next;
    }
    if (tmp != null) { // 找到目標節點
        IntNode newNode = new IntNode(el, tmp.next, tmp);
        if (tmp.next != null) {
            tmp.next.prev = newNode;
        } else {
            tail = newNode; // 如果 tmp 是尾節點，更新 tail
        }
        tmp.next = newNode;
    }
}

這個操作的步驟如下：
1. 遍歷鏈表找到值為 `afterEl` 的節點。
2. 如果找到目標節點，創建新節點並插入到該節點之後。
3. 調整新節點與相鄰節點的連結，並根據情況更新 `tail`。

### 2.2 刪除操作

#### 2.2.1 刪除頭部節點

刪除頭部節點的時間複雜度為 O(1)。

public int deleteFromHead() {
    if (!isEmpty()) {
        int el = head.info;
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        return el;
    } else {
        return 0; // 或拋出異常
    }
}

這個操作的步驟如下：
1. 如果鏈表不為空，則取得頭部節點的資料值。
2. 如果鏈表只有一個節點，將 `head` 和 `tail` 同時設為 `null`。
3. 如果鏈表有多個節點，將 `head` 移動到下一個節點，並將新的頭節點的 `prev` 設為 `null`。
4. 返回刪除的資料值。

#### 2.2.2 刪除尾部節點

刪除尾部節點只需調整 `tail` 和 `tail.prev` 之間的連結，不需要遍歷整個鏈表，因此時間複雜度為 O(1)。**BUT! SLL的時間複雜度為 O(n)，因為我們需要遍歷到倒數第二個節點。**

public int deleteFromTail() {
    if (!isEmpty()) {
        int el = tail.info;
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        return el;
    } else {
        return 0; // 或拋出異常
    }
}

這個操作的步驟如下：
1. 如果鏈表不為空，取得尾部節點的資料值。
2. 如果鏈表只有一個節點，將 `head` 和 `tail` 同時設為 `null`。
3. 如果鏈表有多個節點，將 `tail` 移動到前一個節點，並將新的尾節點的 `next` 設為 `null`。
4. 返回刪除的資料值。

#### 2.2.3 刪除特定節點

public int delete(int el) {
    IntNode tmp = head;
    while (tmp != null && tmp.info != el) {
        tmp = tmp.next;
    }
    if (tmp != null) { // 找到目標節點
        if (tmp == head) {
            return deleteFromHead();
        } else if (tmp == tail) {
            return deleteFromTail();
        } else {
            tmp.prev.next = tmp.next;
            tmp.next.prev = tmp.prev;
            return tmp.info;
        }
    }
    return 0; // 或拋出異常
}

這個操作的步驟如下：
1. 遍歷鏈表找到值為 `el` 的節點。
2. 如果找到節點，根據其位置（頭部、尾部或中間）進行刪除操作：
- 如果是頭部節點，使用 `deleteFromHead()`。
- 如果是尾部節點，使用 `deleteFromTail()`。
- 如果在中間，調整前後節點的 `next` 和 `prev` 連結，將其從鏈表中移除。

### 2.3 搜索操作

public int find(int el) {
    IntNode tmp;
    for (tmp = head; tmp != null && tmp.info != el; tmp = tmp.next);
    if (tmp == null) {
        return 0; // 或拋出異常
    } else {
        return tmp.info;
    }
}

這個操作的步驟如下：
1. 從 `head` 開始遍歷鏈表，每次移動到下一個節點 `tmp.next`，直到找到與 `el` 相等的資料值或遍歷到鏈表尾部（即 `tmp == null`）。
2. 如果找不到節點，返回 `0`（或拋出異常），如果找到則返回節點的 `info` 值。

### 2.4 完整程式碼 Demo

class IntNode {
    int info;
    IntNode next = null, prev = null;

    IntNode() {
    }

    IntNode(int info) {
        this(info, null, null);
    }

    IntNode(int info, IntNode next, IntNode prev) {
        this.info = info;
        this.next = next;
        this.prev = prev;
    }
}

class DLL {
    private IntNode head, tail;

    // constructor
    public DLL() {
        head = tail = null;
    }

    // helpers
    public boolean isEmpty() {
        return head == null;
    }

    public void setToNull() {
        head = tail = null;
    }

    public int firstInfo() {
        if (!isEmpty()) {
            return head.info;
        } else {

            return 0;
        }
    }

    public void printing() {
        if (isEmpty()) {
            System.out.println("List is empty.");
            return;
        }
        IntNode temp = head;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.print(temp.info + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    // ADD METHODS
    public void addToHead(int info) {
        if (!isEmpty()) {
            head = new IntNode(info, head, null);
            head.next.prev = head;
        } else {
            head = tail = new IntNode(info);
        }
    }

    public void addFromTail(int info) {
        if (!isEmpty()) {
            tail = new IntNode(info, null, tail);
            tail.prev.next = tail;
        } else {
            head = tail = new IntNode(info);
        }
    }

    public void insertAfter(int info, int key) {
        IntNode temp = head;
        while (temp != null && temp.info != key) {
            temp = temp.next;
        } // key

        if (temp != null) {
            IntNode newNode = new IntNode(info, temp.next, temp); // new IntNode
            if (temp.next != null) {
                temp.next.prev = newNode;
            } else {
                tail = newNode;
            } // prev
            temp.next = newNode; // next
        }
    } // key => new IntNode => next&prev

    // DELETE METHODS
    public int deleteFromHead() {
        if (!isEmpty()) {
            int deletedInfo = head.info;
            if (head == tail) {
                head = tail = null;
            } else {
                head = head.next;
                head.prev = null;
            }
            return deletedInfo;
        } else {
            System.out.println("List is empty.");
            return 0;
        }
    }

    public int deleteFromTail() {
        if (!isEmpty()) {
            int deletedInfo = tail.info;
            if (head == tail) {
                head = tail = null;
            } else {
                tail = tail.prev;
                tail.next = null;
            }
            return deletedInfo;
        } else {
            System.out.println("List is empty.");
            return 0;
        }
    }

    public int delete(int key) {
        IntNode temp = head;
        while (temp != null && temp.info != key) {
            temp = temp.next;
        } // key
        if (temp != null) {
            if (temp == head) {
                return deleteFromHead();
            } else if (temp == tail) {
                return deleteFromTail();
            } else {
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
                return temp.info;
            }
        }
        return 0;
    }

    // FIND METHOD
    public int find(int key) {
        IntNode temp = head;
        while (temp != null && temp.info != key) {
            temp = temp.next;
        } // key

        if (temp == null) {
            return 0;
        } else {
            return temp.info;
        }
    }

}

public class DS {
    public static void main(String[] args) {
        DLL list = new DLL();
        list.addToHead(0);
        list.addFromTail(2);
        list.insertAfter(1, 0);
        list.printing();
        System.out.println("Finding: " + list.find(2));
        list.deleteFromHead();
        list.deleteFromTail();
        list.delete(1);
        list.printing();
    }
}

#### Output:
:::success
**0 1 2
Finding: 2
List is empty.**
:::

## 3. 應用實例 - 多項式加減乘除

import java.io.*;
import java.util.*;

// 節點類別，用於存儲多項式的每一項
class Node {
    int coefficient;
    int exponent;
    Node prev;
    Node next;

    public Node(int coefficient, int exponent) {
        this.coefficient = coefficient;
        this.exponent = exponent;
        this.prev = null;
        this.next = null;
    }
}

// 多項式類別，使用雙向鏈結串列實現
class Polynomial {
    Node head;
    Node tail;

    public Polynomial() {
        head = null;
        tail = null;
    }

    // 新增項到多項式
    public void addTerm(int coefficient, int exponent) {
        Node newNode = new Node(coefficient, exponent);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // 從字串解析多項式
    public void parsePolynomial(String input) {
        String[] terms = input.split("(?=[-+])");
        for (String term : terms) {
            term = term.trim();
            int coefficient = 1;
            int exponent = 0;

            if (term.contains("x")) {
                String[] parts = term.split("x");
                if (!parts[0].isEmpty() && !parts[0].equals("+") && !parts[0].equals("-")) {
                    coefficient = Integer.parseInt(parts[0]);
                } else if (parts[0].equals("-")) {
                    coefficient = -1;
                }

                if (parts.length > 1 && parts[1].startsWith("^")) {
                    exponent = Integer.parseInt(parts[1].substring(1));
                } else {
                    exponent = 1;
                }
            } else {
                coefficient = Integer.parseInt(term);
            }

            addTerm(coefficient, exponent);
        }
    }

    // 多項式相加
    public Polynomial add(Polynomial other) {
        Polynomial result = new Polynomial();
        Node p = this.head;
        Node q = other.head;

        while (p != null && q != null) {
            if (p.exponent > q.exponent) {
                result.addTerm(p.coefficient, p.exponent);
                p = p.next;
            } else if (p.exponent < q.exponent) {
                result.addTerm(q.coefficient, q.exponent);
                q = q.next;
            } else {
                int sum = p.coefficient + q.coefficient;
                if (sum != 0) {
                    result.addTerm(sum, p.exponent);
                }
                p = p.next;
                q = q.next;
            }
        }

        while (p != null) {
            result.addTerm(p.coefficient, p.exponent);
            p = p.next;
        }

        while (q != null) {
            result.addTerm(q.coefficient, q.exponent);
            q = q.next;
        }

        return result;
    }

    // 多項式相減
    public Polynomial subtract(Polynomial other) {
        Polynomial result = new Polynomial();
        Node p = this.head;
        Node q = other.head;

        while (p != null && q != null) {
            if (p.exponent > q.exponent) {
                result.addTerm(p.coefficient, p.exponent);
                p = p.next;
            } else if (p.exponent < q.exponent) {
                result.addTerm(-q.coefficient, q.exponent);
                q = q.next;
            } else {
                int diff = p.coefficient - q.coefficient;
                if (diff != 0) {
                    result.addTerm(diff, p.exponent);
                }
                p = p.next;
                q = q.next;
            }
        }

        while (p != null) {
            result.addTerm(p.coefficient, p.exponent);
            p = p.next;
        }

        while (q != null) {
            result.addTerm(-q.coefficient, q.exponent);
            q = q.next;
        }

        return result;
    }

    // 多項式相乘
    public Polynomial multiply(Polynomial other) {
        Polynomial result = new Polynomial();
        Node p = this.head;

        while (p != null) {
            Node q = other.head;
            while (q != null) {
                int coef = p.coefficient * q.coefficient;
                int exp = p.exponent + q.exponent;
                result.addTerm(coef, exp);
                q = q.next;
            }
            p = p.next;
        }

        return result.simplify();
    }

    // 簡化多項式（合併同類項）
    private Polynomial simplify() {
        Polynomial simplified = new Polynomial();
        Map<Integer, Integer> terms = new TreeMap<>(Collections.reverseOrder());

        Node current = this.head;
        while (current != null) {
            terms.put(current.exponent, terms.getOrDefault(current.exponent, 0) + current.coefficient);
            current = current.next;
        }

        for (Map.Entry<Integer, Integer> entry : terms.entrySet()) {
            if (entry.getValue() != 0) {
                simplified.addTerm(entry.getValue(), entry.getKey());
            }
        }

        return simplified;
    }

    // 將多項式轉換為字串
    @Override
    public String toString() {
        if (head == null) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        Node current = head;
        boolean isFirst = true;

        while (current != null) {
            if (current.coefficient != 0) {
                if (!isFirst && current.coefficient > 0) {
                    sb.append("+");
                }

                if (current.coefficient != 1 || current.exponent == 0) {
                    sb.append(current.coefficient);
                }

                if (current.exponent != 0) {
                    sb.append("x");
                    if (current.exponent != 1) {
                        sb.append("^").append(current.exponent);
                    }
                }

                isFirst = false;
            }
            current = current.next;
        }

        return sb.toString();
    }
}

public class PolynomialOperations {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        Polynomial poly1 = new Polynomial();
        Polynomial poly2 = new Polynomial();

        while (true) {
            System.out.println("請選擇輸入方式：");
            System.out.println("1. 從檔案讀取");
            System.out.println("2. 手動輸入");
            System.out.print("請輸入選擇 (1 或 2)：");
            int choice = scanner.nextInt();
            scanner.nextLine(); // 消耗換行符

            if (choice == 1) {
                System.out.print("請輸入檔案名稱：");
                String filename = scanner.nextLine();
                readFromFile(filename, poly1, poly2);
            } else if (choice == 2) {
                System.out.print("請輸入第一個多項式：");
                String input1 = scanner.nextLine();
                poly1.parsePolynomial(input1);

                System.out.print("請輸入第二個多項式：");
                String input2 = scanner.nextLine();
                poly2.parsePolynomial(input2);
            } else {
                System.out.println("無效的選擇，請重新輸入。");
                continue;
            }

            while (true) {
                System.out.println("\n請選擇操作：");
                System.out.println("1. 相加");
                System.out.println("2. 相減");
                System.out.println("3. 相乘");
                System.out.println("4. 輸入新的多項式");
                System.out.println("5. 結束程式");
                System.out.print("請輸入選擇：");
                int operation = scanner.nextInt();
                scanner.nextLine(); // 消耗換行符

                if (operation == 1) {
                    Polynomial result = poly1.add(poly2);
                    System.out.println("結果：(" + poly1 + ") + (" + poly2 + ") = " + result);
                } else if (operation == 2) {
                    Polynomial result = poly1.subtract(poly2);
                    System.out.println("結果：(" + poly1 + ") - (" + poly2 + ") = " + result);
                } else if (operation == 3) {
                    Polynomial result = poly1.multiply(poly2);
                    System.out.println("結果：(" + poly1 + ") * (" + poly2 + ") = " + result);
                } else if (operation == 4) {
                    break;
                } else if (operation == 5) {
                    System.out.println("程式結束。");
                    return;
                } else {
                    System.out.println("無效的選擇，請重新輸入。");
                }
            }
        }
    }

    // 從檔案讀取多項式
    private static void readFromFile(String filename, Polynomial poly1, Polynomial poly2) throws IOException {
        try (BufferedReader reader = new BufferedReader(new FileReader(filename))) {
            String line1 = reader.readLine();
            String line2 = reader.readLine();

            if (line1 != null && line2 != null) {
                poly1.parsePolynomial(line1);
                poly2.parsePolynomial(line2);
                System.out.println("已從檔案讀取多項式：");
                System.out.println("多項式1：" + poly1);
                System.out.println("多項式2：" + poly2);
            } else {
                System.out.println("檔案格式錯誤或檔案為空。");
            }
        } catch (FileNotFoundException e) {
            System.out.println("找不到指定的檔案。");
        }
    }
}