package linkedlist;

public class DoubleLinkedListDemo {

	public static void main(String[] args) {
		// 測(cè)試
		System.out.println("雙向鏈表的測(cè)試");
		// 創(chuàng)建節(jié)點(diǎn)
		Node node1 = new Node(1, "道明寺");
		Node node2 = new Node(2, "花澤類");
		Node node3 = new Node(3, "西門總二郎");
		Node node4 = new Node(4, "美作玲");
		// 創(chuàng)建一個(gè)雙向鏈表
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
		// 添加節(jié)點(diǎn)
		doubleLinkedList.addByOrder(node1);
		doubleLinkedList.addByOrder(node4);
		doubleLinkedList.addByOrder(node3);
		doubleLinkedList.addByOrder(node2);
		// 顯示排序后的雙向鏈表
		doubleLinkedList.list();
	}
}

// 創(chuàng)建一個(gè)雙向鏈表的類
class DoubleLinkedList {
	// 先初始化頭節(jié)點(diǎn)，頭節(jié)點(diǎn)不動(dòng)
	private Node head = new Node(0, "");
	
	// 返回頭節(jié)點(diǎn)
	public Node getHead() {
		return head;
	}
	
	// 添加節(jié)點(diǎn)時(shí)，根據(jù)編號(hào)將節(jié)點(diǎn)插入到指定位置
	// 如果有這個(gè)編號(hào)，則添加失敗，并給出提示
	public void addByOrder(Node node) {
		// 頭節(jié)點(diǎn)不能動(dòng)，通過(guò)一個(gè)輔助指針（變量）幫助找到需要添加的位置
		Node temp = head;
		boolean flag = false;	// flag標(biāo)志添加的編號(hào)是否存在，默認(rèn)為false
		while(true) {
			if(temp.next == null) {
				break;
			}
			if(temp.next.no > node.no) {
				break;
			}
			if(temp.next.no == node.no) {
				flag = true;
				break;
			}
			temp = temp.next;	// 遍歷鏈表
		}
		if(flag) {
			System.out.printf("輸入的編號(hào)%d已經(jīng)存在,不能加入\n", node.no);
		}
		else {
			// 為防止出現(xiàn)空指針的情況，需要對(duì)temp節(jié)點(diǎn)位置進(jìn)行判斷
			// 若雙向鏈表尚未到達(dá)尾端，則需要將node節(jié)點(diǎn)與其相鄰的后面的節(jié)點(diǎn)進(jìn)行連接
			if(temp.next != null) {
				node.next = temp.next;
				temp.next.pre = node;
			}
			// 無(wú)論雙向鏈表是否到達(dá)尾端，都需要將node節(jié)點(diǎn)與其相鄰的前面的節(jié)點(diǎn)進(jìn)行連接
			temp.next = node;
			node.pre = temp;
		}
	}
	
	// 遍歷雙向鏈表的方法
	// 顯示鏈表【遍歷】
	public void list() {
		// 判斷鏈表是否為空
		if(head.next == null) {
			System.out.println("鏈表為空");
			return;
		}
		// 因?yàn)轭^節(jié)點(diǎn)不能動(dòng)，需要一個(gè)輔助變量來(lái)遍歷
		Node temp = head.next;
		while (true) {
			// 判斷是否到鏈表最后
			if(temp == null)
				break;
			// 輸出節(jié)點(diǎn)的信息
			System.out.println(temp);
			// 將temp后移
			temp = temp.next;
		}
	}
}

// 創(chuàng)建一個(gè)雙向鏈表的類
// 定義Node，每個(gè)Node對(duì)象就是一個(gè)節(jié)點(diǎn)
class Node {
	public int no;
	public String name;
	public Node next;	// 指向下一個(gè)節(jié)點(diǎn)，默認(rèn)為null
	public Node pre;	// 指向前一個(gè)節(jié)點(diǎn)，默認(rèn)為null
	// 構(gòu)造器
	public Node(int no, String name) {
		this.no = no;
		this.name = name;
	}
	// 為了顯示方便，重新toString
	@Override
	public String toString() {
		return "Node [no=" + no + ", name=" + name +"]";
	}
}