package linkedlist;

public class DoubleLinkedListDemo {

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

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

// 創(chuàng)建一個雙向鏈表的類
// 定義Node，每個Node對象就是一個節(jié)點
class Node {
	public int no;
	public String name;
	public Node next;	// 指向下一個節(jié)點，默認為null
	public Node pre;	// 指向前一個節(jié)點，默認為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 +"]";
	}
}