# 雙向鏈結串列(Doubly Linked List)

**雙向鏈結串列示意圖**


可以很明顯的發現，查找的方向從單向變為雙向。

## 遍歷、添加、修改、刪除的操作思路

1. **遍歷**方式和單向鏈結串列一樣，只是可以向前也可以向後查找
2. **添加**(默認加到雙向鏈結串列的最後)
-- 先找到雙向鏈結串列的最後節點
-- `temp.next = newHeroNode`
-- `newHeroNode.prev = temp`
3. **修改**的思路和原來的單向鏈結串列一樣
4. **刪除**
-- 因為是雙向，因此我們可以實現自我刪除某個節點
-- 直接找到要刪除的節點，比如 temp
-- `temp.prev.next = temp.next`
-- `temp.next.prev = temp.prev`

## 代碼實現

因為基本和單向鏈結串列差不多，僅有刪除和新增的部分有些微的修改，因此不再多做解釋。

public class DoublyLinkedListDemo {
    public static void main(String[] args) {
        System.out.println("雙向鏈結串列的測試");
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及時雨");
        HeroNode2 hero2 = new HeroNode2(2, "盧俊義", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吳用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林沖", "豹子頭");

        DoublyLinkedList doublyLinkedList = new DoublyLinkedList();

        doublyLinkedList.add(hero1);
        doublyLinkedList.add(hero4);
        doublyLinkedList.add(hero2);
        doublyLinkedList.add(hero3);
        doublyLinkedList.list();

        System.out.println("===修改測試===");
        HeroNode2 newHeroNode = new HeroNode2(4, "公孫勝", "入雲龍");
        doublyLinkedList.updata(newHeroNode);
        doublyLinkedList.list();

        System.out.println("===刪除測試===");
        doublyLinkedList.delete(2);
        doublyLinkedList.list();
    }
}

class DoublyLinkedList {
    //先初始化一個頭節點,頭節點不要動,不存放具體數據
    private HeroNode2 head = new HeroNode2(0, "", "");
    public HeroNode2 getHead() {
        return head;
    }

    //遍歷雙向鏈結串列
    public void list() {
        if(head.next == null) {
            System.out.println("鏈結串列為空");
            return;
        }
        HeroNode2 temp = head.next;
        while(true) {
            if(temp == null) {
                break;
            }
            //輸出節點訊息
            System.out.println(temp);
            //將temp後移, 不然是死循環
            temp = temp.next;
        }
    }

    //添加數據到雙向鏈結串列的最後
    public void add(HeroNode2 heroNode) {
        //因為head節點不能動,因此我們需要一個輔助遍歷 temp
        HeroNode2 temp = head;
        //遍歷鏈結串列,找到最後
        while(true) {
            if (temp.next == null) {
                break;
            }

            temp = temp.next; //沒找到就將temp後移一個節點
        }
        //當退出while循環時,temp就指向了鏈結串列的最後
        //形成一個雙向鏈結串列
        temp.next = heroNode;
        heroNode.prev = temp;
    }

    //修改節點內容
    public void updata(HeroNode2 newHeroNode) {
        if(head.next == null) {
            System.out.println("鏈結串列為空");
            return;
        }
        //找到需要修改的節點
        //定義一個輔助變數
        HeroNode2 temp = head.next;
        boolean flag = false; //是否找到該節點
        while(true) {
            if (temp == null) break; //已遍歷結束
            if (temp.no == newHeroNode.no) { //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根據flag 判斷是否找到
        if(flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else {
            System.out.printf("沒有找到編號 %d 的節點, 不能修改\n",newHeroNode.no);
        }
    }

    //刪除節點
    public void delete(int no) {
        HeroNode2 temp = head.next;
        boolean flag = false; 
        if(head.next == null) {
            System.out.println("鏈結串列為空,無法刪除");
            return;
        }
        while(true) {
            if (temp == null) break; //已遍歷結束
            if(temp.no == no) { //要刪除的節點為第一個節點
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if(flag) {
            temp.prev.next = temp.next;
            //如果是最後一個節點就不需要執行下面這句話,否則會出現空指針異常
            if(temp.next != null) {
                temp.next.prev = temp.prev;
            }
            System.out.printf("刪除了 %d 節點.\n",no);
        }else {
            System.out.printf("沒有找到編號 %d 的節點, 不能刪除\n",no);
        }
    }

}

class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next; //指向下一個節點, 默認為null
    public HeroNode2 prev; //指向前一個節點, 默認為null
    //構造函數
    public HeroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    //重寫toString
    @Override
    public String toString() {
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }

}


### 有序添加

public void addByOrder(HeroNode2 heroNode) {
        HeroNode2 temp = head;
        boolean flag = false; //添加的編號是否已經存在

        while(true) {
            if(temp.next == null) break;
            if(temp.next.no > heroNode.no) { //位置找到, 就在temp的後面插入
                break;
            }else if(temp.next.no == heroNode.no) { //編號已經存在
                flag = true;
                break;
            }
            temp = temp.next;
        }

        //判斷flag的值
        if(flag) {
            System.out.printf("準備添加的英雄編號 %d 已經存在，不能添加\n",heroNode.no);
        }else{
            heroNode.next = temp.next;
            temp.next = heroNode;
            heroNode.prev = temp;
        }
    }


## 約瑟夫問題(Josephus Problem)

設編號為1,2,...n的n個人圍坐一圈，約定編號為k(1<=k<=n)的人從1開始報數，數到m的人出列，依此類推直到所有人出列為止，由此產生一個出隊編號的序列。

**提示：**
用一個不帶頭結點的循環鏈結串列來處理，先構成一個有n個結點的單循環鏈結串列，然後由k結點起從1開始計數，計到m時，對應結點從鏈結串列中刪除，然後再從被刪除結點的下一個結點又從1開始報數，直到最後一個結點從鏈結串列中刪除演算法結束。

**設 n = 5 , k = 1(從1開始數), m = 2(數到第2個出隊列)**

如下圖所示，出隊列順序為：
**2 -> 4 -> 1 -> 5 -> 3**


### 分析圖解和實現
這部分建議看 [EP28](https://www.bilibili.com/video/BV16t411g7wa?p=28) 聽老師講解思路，用文字說明不太容易懂。

### 構建一個單項的環形鏈結串列
**思路**
1. 先創建第一個節點，讓 first 指向該節點，並形成一個環形
2. 後面當我們每創建一個新的節點，就把該節點加入到已有的環形鏈結串列中
(每個節點的next指向下一個節點，最後一個節點的next指向第一個節點形成一個環)

#### 遍歷環形鏈結串列
1. 先讓一個輔助變數指向 first 節點
2. 然後通過一個 while 循環遍歷該環形鏈結串列 `cur.next == first`

根據使用者的輸入，生成一個節點出隊列的順序：
1. 需求創建一個輔助變數 helper，事先應該指向環形鏈結串列的最後節點
2. 先讓 first 和 helper移動 k-1 次
3. 當節點報數時，讓first和helper指針同時移動 m-1 次
4. 這時就可以將first 指向節點出隊列
-- `first = first.next`
-- `helper.next = first`
原先first 指向的節點就沒有任何引用(出隊列了)，被垃圾回收。

public class JosephusDemo {
    public static void main(String[] args) {
        CircularSinglyLinkedList csll = new CircularSinglyLinkedList();
        csll.addNode(5); // 加入5個節點
        csll.showNode();
        System.out.println("===出隊列順序===");
        csll.countNode(1, 2, 5);
    }
}

// 創建一個環形的單向鏈結串列
class CircularSinglyLinkedList {
    // 創建一個first節點, 當前沒有編號
    private Node first = new Node(-1);

    // 添加節點, 構建成一個環形的鏈結串列
    public void addNode(int nums) {
        // nums 數據校驗
        if (nums < 1) {
            System.out.println("nums值不正確! ");
            return;
        }

        Node cur = null; // 輔助變數 幫助構建環形鏈結串列
        // 使用for循環創建環形鏈結串列
        for (int i = 1; i <= nums; i++) {
            // 根據編號創建節點
            Node child = new Node(i);
            // 若為第一個節點
            if (i == 1) {
                first = child;
                first.setNext(first); // 構成環
                cur = first; // 讓cur 指向第一個節點
            } else {
                cur.setNext(child);
                child.setNext(first);
                cur = child;
            }

        }
    }

    // 遍歷當前環形鏈結串列
    public void showNode() {
        // 判斷鏈結串列是否為空
        if (first == null) {
            System.out.println("鏈結串列為空");
            return;
        }
        // 因為 first不能動,因此需要使用一個輔助指針
        Node cur = first;
        while (true) {
            System.out.printf("節點編號 %d \n", cur.getNo());
            if (cur.getNext() == first) { // 遍歷完畢
                break;
            }
            cur = cur.getNext(); // 往後遍歷
        }
    }

    /**
     * 
     * @param startNo  表示從第幾個node開始數
     * @param countNum 表示數幾次
     * @param nums     表示最初有多少個node在環中
     */
    // 根據使用者的輸入,計算出節點出隊列的順序
    public void countNode(int startNo, int countNum, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("參數輸入有誤，請重新輸入");
            return;
        }
        // 創建一個輔助指針,幫助完成node出隊列
        Node helper = first;
        while (true) {
            if (helper.getNext() == first) { // helper指向最後一個節點
                break;
            }
            helper = helper.getNext();
        }

        //先讓first和helper 移動startNo-1次
        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        //當節點報數時，讓first和helper指針同時移動 countNum- 1次 然後出隊列
        while(true) {
            if(helper == first) {
                //說明環中只有一個node
                break;
            }
            //讓 first和helper同時移動 countNum -1次
            for (int i = 0; i < countNum -1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //這時 first 指向的節點就是 要出隊列 的節點
            System.out.printf("節點 %d 出隊列\n",first.getNo());
            //將first指向的節點出隊列
            first = first.getNext(); //出隊列後往下一個節點繼續數
            helper.setNext(first); //把helper歸回第一個數的節點繼續遍歷
        }
        System.out.printf("最後留在環中的節點為 %d \n",first.getNo());
    }
}

// 創建一個Node類,表示一個節點
class Node {
    private int no; // 編號
    private Node next; // 指向下一個節點

    public Node(int no) {
        this.no = no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }
}


**個人理解**

* first 指向第一個數的節點
* helper 用於遍歷節點

假設今天**n = 5 (總共5個節點), k = 1 (從1開始數) , m = 2 (數到2出隊列)**

1. 那麼first要指向第一個數的節點，所以是 1，helper 也先設為 first
2. 然後將 first,helper 遍歷 2-1次

**為什麼first也要跟著遍歷，它不是要指向第一個節點嗎?**

那是因為當你數到 2 節點出隊列後，下一次就是從出隊列的後一個節點開始數，
所以 first 也需要跟著 helper 一起遍歷，如此一來，當 2 號節點出隊列後，first會指向 3，而helper也指向3 重新開始遍歷。

以此類推。

**為什麼明明要數 2 次(m = 2)，卻只需要遍歷 2-1(m - 1)次?**

如果會有這個疑惑就是對約瑟夫問題還沒理解，這裡的 m 代表數到幾出隊列，而開始數的那個節點也要計算，所以從 1節點 開始數，數到 2 就是 2號節點。

這些問題搞清楚之後回去看程式碼應該會很容易理解。