public class DoubleLinkedListDemo {
	public static void main(String[] args) {
		// 測試
		System.out.println("雙向鏈表的測試");
		// 先創(chuàng)建節(jié)點(diǎn)
		HeroNode2 hero1 = new HeroNode2(1, "宋江", "及時(shí)雨");
		HeroNode2 hero2 = new HeroNode2(2, "盧俊義", "玉麒麟");
		HeroNode2 hero3 = new HeroNode2(3, "吳用", "智多星");
		HeroNode2 hero4 = new HeroNode2(4, "林沖", "豹子頭");
		// 創(chuàng)建一個(gè)雙向鏈表
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
		// 加入
		doubleLinkedList.add(hero1);
		doubleLinkedList.add(hero2);
		doubleLinkedList.add(hero3);
		doubleLinkedList.add(hero4);
		doubleLinkedList.list();
		// 修改
		HeroNode2 newHeroNode = new HeroNode2(4, "公孫勝", "入云龍");
		doubleLinkedList.update(newHeroNode);
		System.out.println("修改后的鏈表情況");
		doubleLinkedList.list();
		// 刪除
		doubleLinkedList.del(3);
		System.out.println("刪除后的鏈表情況~~");
		doubleLinkedList.list();
	}
}
//創(chuàng)建一個(gè)雙向鏈表的類
class DoubleLinkedList {
	// 先初始化一個(gè)頭節(jié)點(diǎn)，頭節(jié)點(diǎn)不要?jiǎng)?，不存放具體的數(shù)據(jù)
	private HeroNode2 head = new HeroNode2(0, "", "");
	// 返回頭節(jié)點(diǎn)
	public HeroNode2 getHead() {
		return head;
	}
	// 顯示鏈表[遍歷]
	public void list() {
		// 判斷鏈表是否為空
		if (head.next == null) {
			System.out.println("鏈表為空");
			return;
		}
		// 因?yàn)轭^節(jié)點(diǎn)，不能動(dòng)，因此我們需要一個(gè)輔助變量來遍歷
		HeroNode2 temp = head.next;
		while (true) {
			// 判斷是否到鏈表最后
			if (temp == null) {
				break;
			}
			// 輸出節(jié)點(diǎn)的信息
			System.out.println(temp);
			// 將temp后移，一定小心
			temp = temp.next;
		}
	}
	// 添加一個(gè)節(jié)點(diǎn)到雙向鏈表的最后
	public void add(HeroNode2 heroNode) {
		// 因?yàn)閔ead節(jié)點(diǎn)不能動(dòng)，因此我們需要一個(gè)輔助變量temp
		HeroNode2 temp = head;
		// 遍歷鏈表，找到最后
		while (true) {
			// 找到鏈表的最后
			if (temp.next == null) {
				break;
			}
			// 如果沒有找到最后，將temp后移
			temp = temp.next;
		}
		// 當(dāng)退出while循環(huán)時(shí)，temp就指向了鏈表的最后
		// 形成一個(gè)雙向鏈表
		temp.next = heroNode;
		heroNode.pre = temp;
	}
	// 修改一個(gè)節(jié)點(diǎn)的內(nèi)容，雙向鏈表的節(jié)點(diǎn)內(nèi)容修改和單向鏈表一樣
	// 只是節(jié)點(diǎn)類型改成HeroNode2
	public void update(HeroNode2 newHeroNode) {
		// 判斷是否空
		if (head.next == null) {
			System.out.println("鏈表為空~~");
			return;
		}
		// 找到需要修改的節(jié)點(diǎn)，根據(jù)no編號
		// 定義一個(gè)輔助變量
		HeroNode2 temp = head.next;
		boolean flag = false;// 表示是否找到該節(jié)點(diǎn)
		while (true) {
			if (temp == null) {
				break;// 已經(jīng)遍歷完鏈表
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// 根據(jù)flag判斷是否找到要修改的節(jié)點(diǎn)
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {// 沒有找到
			System.out.printf("沒有找到編號 %d 的節(jié)點(diǎn)，不能修改\n", newHeroNode.no);
		}
	}
	// 從雙向鏈表中刪除一個(gè)節(jié)點(diǎn)
	// 說明
	// 1. 對于雙向鏈表，我們可以直接找到要?jiǎng)h除的這個(gè)節(jié)點(diǎn)
	// 2. 找到后，自我刪除即可
	public void del(int no) {
		// 判斷當(dāng)前鏈表是否為空
		if (head.next == null) {// 空鏈表
			System.out.println("鏈表為空，無法刪除");
			return;
		}
		HeroNode2 temp = head.next;// 輔助變量(指針),指向第一個(gè)節(jié)點(diǎn)(與單向鏈表不同)
		boolean flag = false;// 標(biāo)志是否找到待刪除節(jié)點(diǎn)
		while (true) {
			if (temp.next == null) {// 已經(jīng)到鏈表的最后節(jié)點(diǎn)的next
				break;
			}
			if (temp.next.no == no) {
				// 找到的待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)temp
				flag = true;
				break;
			}
			temp = temp.next;// temp后移，遍歷
		}
		// 判斷flag
		if (flag) {// 找到
			// 可以刪除
			temp.pre.next = temp.next;
			// 如果是最后一個(gè)節(jié)點(diǎn)，就不需要執(zhí)行下面的這句話，否則出現(xiàn)空指針
			if (temp.next != null) {
				temp.next.pre = temp.pre;
			}
		} else {
			System.out.printf("要?jiǎng)h除的 %d 節(jié)點(diǎn)不存在\n", no);
		}
	}
}
//定義HeroNode2,每個(gè)HeroNode對象就是一個(gè)節(jié)點(diǎn)
class HeroNode2 {
	public int no;
	public String name;
	public String nickname;
	public HeroNode2 next;// 指向下一個(gè)節(jié)點(diǎn),默認(rèn)為null
	public HeroNode2 pre;// 指向前一個(gè)節(jié)點(diǎn),默認(rèn)為null
	// 構(gòu)造器
	public HeroNode2(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}
	// 為了顯示方便，我們重寫toString
	@Override
	public String toString() {
		return "HeroNode2 [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
}

public class Josepfu {
	public static void main(String[] args) {
		// 測試看看構(gòu)建環(huán)形鏈表，和遍歷是否ok
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);// 加入5個(gè)小孩節(jié)點(diǎn)
		circleSingleLinkedList.showBoy();
		// 測試小孩出圈是否正確
		circleSingleLinkedList.countBoy(1, 2, 5);// 2->4->1->5->3
	}
}
//創(chuàng)建一個(gè)環(huán)形的單向鏈表
class CircleSingleLinkedList {
	// 創(chuàng)建一個(gè)first節(jié)點(diǎn)，當(dāng)前沒有編號
	private Boy first = null;
 
	// 添加小孩節(jié)點(diǎn)，構(gòu)建一個(gè)環(huán)形的鏈表
	public void addBoy(int nums) {
		// nums 做一個(gè)數(shù)據(jù)校驗(yàn)
		if (nums < 1) {
			System.out.println("nums的值不正確");
			return;
		}
		Boy curBoy = null;// 輔助指針，幫助構(gòu)建環(huán)形鏈表
		// 使用for來創(chuàng)建環(huán)形鏈表
		for (int i = 1; i <= nums; i++) {
			// 根據(jù)編號，創(chuàng)建小孩節(jié)點(diǎn)
			Boy boy = new Boy(i);
			// 如果是第一個(gè)小孩
			if (i == 1) {
				first = boy;
				first.setNext(first);// 構(gòu)成環(huán)(暫時(shí)是一個(gè)節(jié)點(diǎn)的環(huán))
				curBoy = first;// 讓curBoy指向第一個(gè)小孩
			} else {// 這塊的操作看不懂，可以回去看一下當(dāng)時(shí)老師視頻里的流程圖，特別好理解?。。。。。。。。。?
				curBoy.setNext(boy);
				boy.setNext(first);
				curBoy = boy;
			}
		}
	}
	// 遍歷當(dāng)前的環(huán)形鏈表
	public void showBoy() {
		// 判斷鏈表是否為空
		if (first == null) {
			System.out.println("沒有任何小孩~~");
			return;
		}
		// 因?yàn)閒irst不能動(dòng)，因此我們?nèi)匀皇褂靡粋€(gè)輔助指針完成遍歷
		Boy curBoy = first;
		while (true) {
			System.out.printf("小孩的編號 %d \n", curBoy.getNo());
			if (curBoy.getNext() == first) {// 說明已經(jīng)遍歷完畢
				break;
			}
			curBoy = curBoy.getNext();// curBoy后移
		}
	}
	// 根據(jù)用戶的輸入，計(jì)算出小孩出圈的順序
	/**
	 * @param startNo  表示從第幾個(gè)小孩開始數(shù)數(shù)
	 * @param countNum 表示數(shù)幾下
	 * @param nums     表示最初有多少小孩在圈中
	 */
	public void countBoy(int startNo, int countNum, int nums) {
		// 先對數(shù)據(jù)進(jìn)行校驗(yàn)
		if (first == null || startNo < 1 || startNo > nums) {
			System.out.println("參數(shù)輸入有誤，請重新輸入");
			return;
		}
		// 創(chuàng)建一個(gè)輔助指針，幫助完成小孩出圈
		Boy helper = first;
		// 需要?jiǎng)?chuàng)建一個(gè)輔助指針(變量)helper,事先應(yīng)該指向環(huán)形鏈表的最后這個(gè)節(jié)點(diǎn)
		while (true) {
			if (helper.getNext() == first) {// 說明helper指向最后小孩節(jié)點(diǎn)
				break;
			}
			helper = helper.getNext();
		}
		// 小孩報(bào)數(shù)前，先讓first 和 helper 移動(dòng) k - 1次
		for (int j = 0; j < startNo - 1; j++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		// 當(dāng)小孩報(bào)數(shù)時(shí)，讓 first 和 helper 指針同時(shí)的移動(dòng) m -1次，然后出圈
		// 這里是一個(gè)循環(huán)操作，直到圈中只有一個(gè)節(jié)點(diǎn)
		while (true) {
			if (helper == first) {// 說明圈中只有一個(gè)節(jié)點(diǎn)
				break;
			}
			// 讓first 和 helper 指針同時(shí)的移動(dòng) countNum - 1
			for (int j = 0; j < countNum - 1; j++) {
				first = first.getNext();
				helper = helper.getNext();
			}
			// 這時(shí)first指向的節(jié)點(diǎn)，就是要出圈的小孩節(jié)點(diǎn)
			System.out.printf("小孩%d出圈\n", first.getNo());
			// 這時(shí)將first指向的小孩節(jié)點(diǎn)出圈
			first = first.getNext();
			helper.setNext(first);
		}
		System.out.printf("最后留在圈中的小孩編號%d \n", first.getNo());
	}
}
//創(chuàng)建一個(gè)Boy類，表示一個(gè)節(jié)點(diǎn)
class Boy {
	private int no;// 編號
	private Boy next;// 指向下一個(gè)節(jié)點(diǎn)，默認(rèn)null
 
	public Boy(int no) {
		this.no = no;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public Boy getNext() {
		return next;
	}
	public void setNext(Boy next) {
		this.next = next;
	}
}