/**
 * 雙向鏈表的實現
 * @author Skip
 * @version 1.0
 */
public class DoubleNodeList<T> {
 //節點類
 private static class Node<T>{
  Node<T> perv;  //前節點
  Node<T> next;  //后節點
  T data;    //數據

  public Node(T t){
   this.data = t;
  }
 }
 private Node<T> head;  //頭節點
 private Node<T> last;  //尾節點
 private Node<T> other;  //備用節點存放臨時操作
 private int length;  //鏈表長度

 /**
  * 無參構造
  */
 public DoubleNodeList(){
  head = new Node<T>(null);
  last = head;
  length = 0;
 }

 /**
  * 初始化時創建一個節點
  * @param data 數據
  */
 public DoubleNodeList(T data){
  head = new Node<T>(data);
  last = head;
  length = 1;
 }

 /**
  * 添加一個節點
  * @param data 添加的數據
  */
 public void add(T data){
  if(isEmpty()){
   head = new Node<T>(data);
   last = head;
   length++;
  }else{
   //尾插法
   other = new Node<T>(data);
   other.perv = last;
   last.next = other;
   last = other;
   length++;
  }
 }

 /**
  * 在指定數據后插入一個節點
  * @param data 指定的數據
  * @param insertData 插入的數據
  * @return 插入成功返回true,不成功返回false
  */
 public boolean addAfert(T data , T insertData){
  other = head;
  while(other != null){
   if(other.data.equals(data)){
    Node<T> t = new Node<T>(insertData);
    t.perv = other;
    t.next = other.next;
    other.next = t;
    //判斷是否在最后一個節點后添加節點
    if(t.next==null){
     last = t;
    }
    length++;
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 在指定數據前插入一個節點
  * @param data 指定的數據
  * @param insertData 插入的數據
  * @return 插入成功返回true,不成功返回false
  */
 public boolean addBefore(T data, T insertData){
  other = head;
  while(other != null){
   if(other.data.equals(data)){
    Node<T> t = new Node<T>(insertData);
    t.perv = other.perv;
    t.next = other;
    other.perv.next = t;
    length++;
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 獲得索引處的數據
  * @param index 索引
  * @return 數據
  */
 public T get(int index){
  if(index>length || index<0){
   throw new IndexOutOfBoundsException("索引越界:"+index);
  }
  other = head;
  for(int i=0;i<index;i++){
   other = other.next;
  }
  return other.data;
 }

 /**
  * 新值替換舊值
  * @return 成功為true,未找到為false
  */
 public boolean set(T oldValue,T newValue){
  other = head;
  while(other!=null){
   if(other.data.equals(oldValue)){
    other.data = newValue;
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 移除指定的元素
  * @param data 需要移除的元素
  * @return 不存在為false,成功為true
  */
 public boolean remove(T data){
  other = head;
  while(other != null){
   if(other.data.equals(data)){
    other.perv.next = other.next;
    length--;
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 鏈表中是否包含此元素
  * @return 包含為true,不包含為false
  */
 public boolean contains(T data){
  other = head;
  while(other != null){
   if(other.data.equals(data)){
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 獲得最后一個節點的數據
  * @return 最后一個節點的數據
  */
 public T getLast(){
  return last.data;
 }

 /**
  * 獲得第一個節點的數據
  * @return 第一個節點的數據
  */
 public T getFirst(){
  return head.data;
 }

 /**
  * 獲得鏈表的長度
  * @return 長度
  */
 public int getSize(){
  return length;
 }

 /**
  * 是否為空鏈表
  * @return 空鏈表為true,非空鏈表為false
  */
 public boolean isEmpty(){
  return length==0;
 }

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

 /**
  * 輸出鏈表內所有節點
  */
 public void printList(){
  if(isEmpty()){
   System.out.println("空鏈表");
  }else{
   other = head;
   for(int i=0;i<length;i++){
    System.out.print(other.data+" ");
    other = other.next;
   }
   System.out.println();
  }
 }
}