java 实现双向链表实例详解

/**  * 链表节点  * @author Administrator  *  * @param <T>  */ public class ChainNode<T> {  private T data;  //对象编号  private int dataNo;    public ChainNode<T> nextChainNode;  public ChainNode<T> preChainNode;  public ChainNode(T data, ChainNode<T> nextChainNode,    ChainNode<T> preChainNode) {   this.data = data;   this.nextChainNode = nextChainNode;   this.preChainNode = preChainNode;  }        public ChainNode(T data) {   this.data = data;  }      public int getDataNo() {   return dataNo;  }     public void setDataNo(int dataNo) {   this.dataNo = dataNo;  }    public void setData(T data) {   this.data = data;  }     public T getData() {   return data;  }     } 

<pre name="code" class="java">/**  * 链表实现类  * @author Administrator  *  * @param <T>  */ public class Chain<T> {  //头节点  private ChainNode<T> headNode;  //末尾节点指针  private ChainNode<T> lastNode;  private int size;      //创建链表就创建头节点  public Chain() {   this.headNode = new ChainNode<T>(null);   this.lastNode = headNode;     }  //增加一个节点  public void addNode(T data) {   ChainNode<T> node = new ChainNode<T>(data);   if(lastNode != null){    lastNode.nextChainNode = node;    node.preChainNode = node;    node.setDataNo(size);    lastNode = node;    size++;   }  }  //删除指定索引的节点  public void deleteNode(int dataNo) throws Exception {   if(getSize() == 0){    throw new Exception("chain is empty");   }   for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) {    if(node.getDataNo() == dataNo){     node.preChainNode.nextChainNode = node.nextChainNode;     if(node.nextChainNode != null){      node.nextChainNode.preChainNode = node.preChainNode;     }          node.nextChainNode = null;     node.preChainNode = null;     size--;     //重新设置节点的编号     for (ChainNode<T> chainNode = node.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) {      chainNode.setDataNo(chainNode.getDataNo()-1);     }     return;         }   }   throw new Exception("the corresponding data that can not be found");  }  //获取指定索引的节点  public T get(int dataNo) throws Exception {   if(getSize() == 0){    throw new Exception("chain is empty");   }   for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) {    if(node.getDataNo() == dataNo){     return node.getData();    }   }   throw new Exception("the corresponding data that can not be found");  }  //修改对应索引的节点  public void set(int dataNo,T data) throws Exception {   if(getSize() == 0){    throw new Exception("chain is empty");   }   for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) {    if(node.getDataNo() == dataNo){     node.setData(data);     return;    }   }   throw new Exception("the data that is to be modified can not be found");  }  //是否包含对应数据的节点  public boolean isContains(T data) throws Exception {   if(getSize() == 0){    throw new Exception("chain is empty");   }   for (ChainNode<T> chainNode = headNode.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) {    if(chainNode.getData() == data){     return true;    }   }      return false;  }  //获取节点数量（不含头节点）  public int getSize() {   return size;  } } 

public class ChainTest {  public static void main(String[] args) throws Exception{   String oneString = "one";   String twoString = "two";   String threeString = "three";   String fourString = "four";   Chain<String> chain = new Chain<String>();   chain.addNode(oneString);   chain.addNode(twoString);   chain.addNode(threeString);   chain.addNode(fourString);   for (int i = 0; i < chain.getSize(); i++) {    String string2 = chain.get(i);    System.out.println(string2);   }   try {    String string = chain.get(2);    System.out.println("the data of the second node is"+string);    System.out.println(chain.isContains(fourString));    chain.set(1, "haha");    System.out.println("modify chain");    for (int i = 0; i < chain.getSize(); i++) {     String string2 = chain.get(i);     System.out.println(string2);    }        chain.deleteNode(3);    System.out.println("delete one node");    for (int i = 0; i < chain.getSize(); i++) {     String string2 = chain.get(i);     System.out.println(string2);    }   } catch (Exception e) {    // TODO Auto-generated catch block    e.printStackTrace();   }  } } 

onetwothreefourthe data of the second node isthreetruemodify chainonehahathreefourdelete one nodeonehahathree