package org.huhuiyu.datastructures;

/**
 * 鏈表類
 */
public class Link<T> {
	private Node<T> head; // 頭節點
	private int count = 0; // 節點計數

	public Link() {
	}

	/**
	 * 添加節點數據
	 * 
	 * @param nodeData
	 *            要添加的節點數據
	 * @return 添加數據是否成功
	 */
	public boolean add(T nodeData) {
		boolean result = true;
		Node<T> add = new Node<T>(nodeData);
		if (isEmpty()) {
			// 如果鏈表是空的，就直接將添加的節點為頭節點
			head = add;
		}
		else {
			// 否則就添加到結尾的位置
			Node<T> last = getNodeAt(count);
			last.setNext(add);
		}
		count++;
		return result;
	}

	/**
	 * 添加節點到指定位置
	 * 
	 * @param position
	 *            節點位置，必須滿足1到size()+1的閉區間
	 * @param nodeData
	 *            添加的節點
	 * @return 添加是否成功
	 */
	public boolean add(int position, T nodeData) {
		boolean result = true;
		Node<T> add = new Node<T>(nodeData);
		if (isEmpty() || position == 1) {
			// 鏈表為空或者插入的位置是1都表示替換頭節點為新添加的節點
			add.setNext(head);
			head = add;
			count++;
		}
		else if (position > 1 && position <= count + 1) {
			// 如果添加的位置合法，就取出要添加的節點的前一節點和相鄰的節點
			Node<T> nodeBefore = getNodeAt(position - 1);
			Node<T> nodeAfter = nodeBefore.getNext();
			// 設定前一個節點的鏈接為添加的節點
			nodeBefore.setNext(add);
			// 將相鄰的節點設定為添加節點的鏈接節點完成插入的動作
			add.setNext(nodeAfter);
			count++;
		}
		else {
			result = false;
		}
		return result;
	}

	/**
	 * 移除指定位置的節點
	 * 
	 * @param position
	 * @return 被移除的節點的數據
	 */
	public T removeAt(int position) {
		T data = null;
		if (isEmpty()) { // 空鏈表不用刪除
			return null;
		}
		else if (position == 1) { // 刪除頭的方法
			data = head.getData(); // 獲取頭的數據
			head = head.getNext(); // 將頭指向頭的鏈接
			count--;
			return data;
		}
		else if (position > 1 && position <= count) {
			// 要刪除的節點的前一個節點
			Node<T> nodeBefore = getNodeAt(position - 1);
			// 要刪除的節點
			Node<T> nodeRemove = nodeBefore.getNext();
			// 要刪除的節點的后一個節點
			Node<T> nodeAfter = nodeRemove.getNext();
			// 將前一個節點的連接指向后一個節點就完成了刪除的任務
			nodeBefore.setNext(nodeAfter);
			data = nodeRemove.getData();
			count--;
			return data;
		}
		else { // 超出索引范圍也不用刪除
			return null;
		}
	}

	/**
	 * 獲取鏈表存放的節點數量
	 * 
	 * @return 鏈表存放的節點數量
	 */
	public int size() {
		return count;
	}

	/**
	 * 獲取鏈表是否為空
	 * 
	 * @return 是否為空鏈表
	 */
	public boolean isEmpty() {
		return count == 0;
	}

	/**
	 * 清空鏈表
	 */
	public void clear() {
		head = null;
		count = 0;
	}

	/**
	 * 獲取指定位置的的節點數據
	 * 
	 * @param position
	 *            節點位置，必須滿足1=<position<=count+1
	 * @return 指定節點的數據
	 */
	private Node<T> getNodeAt(int position) {
		Node<T> find = head;
		for (int i = 1; i < position; i++) {
			find = find.getNext();
		}
		return find;
	}

	/**
	 * 顯示鏈表數據
	 */
	public void display() {
		for (Node<T> node = head; node != null; node = node.getNext()) {
			System.out.println(node.getData());
		}
	}

	public static void main(String[] args) {
		Link<Integer> link = new Link<Integer>();
		System.out.println("isEmpty:" + link.isEmpty());
		for (int i = 1; i < 10; i++) {
			link.add(i * 10);
		}
		System.out.println("size():" + link.size());
		link.display();
		System.out.println("++++++++++++++++");
		System.out.println("刪除的數據是:" + link.removeAt(1));
		link.display();
		System.out.println("++++++++++++++++");
		System.out.println("添加數據:" + link.add(1, 10));
		link.display();
		System.out.println("++++++++++++++++");
		System.out.println("添加數據:" + link.add(100));
		link.display();
		link.clear();
		System.out.println("isEmpty:" + link.isEmpty());
	}
}