/**
 * 双向链表的实现
 * @author Skip
 * @version 1.0
 */
public class DoubleNodeList {
 //节点类
 private static class Node{
  Node perv;  //前节点
  Node next;  //后节点
  T data;    //数据

  public Node(T t){
   this.data = t;
  }
 }
 private Node head;  //头节点
 private Node last;  //尾节点
 private Node other;  //备用节点存放临时操作
 private int length;  //链表长度

 /**
  * 无参构造
  */
 public DoubleNodeList(){
  head = new Node(null);
  last = head;
  length = 0;
 }

 /**
  * 初始化时创建一个节点
  * @param data 数据
  */
 public DoubleNodeList(T data){
  head = new Node(data);
  last = head;
  length = 1;
 }

 /**
  * 添加一个节点
  * @param data 添加的数据
  */
 public void add(T data){
  if(isEmpty()){
   head = new Node(data);
   last = head;
   length++;
  }else{
   //尾插法
   other = new Node(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 = new Node(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 = new Node(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