java 实现双向链表实例详解

java 实现双向链表实例详解

 双向链表是一个基本的数据结构，在Java中LinkedList已经实现了这种结构，不过作为开发者，也要拥有自己显示这种结构的能力。话不多说，上代码：

    首先是链表的节点类：

/**
 * 链表节点
 * @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();
  }
 }
}

结果：

one
two
three
four
the data of the second node isthree
true
modify chain
one
haha
three
four
delete one node
one
haha
three

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

原文链接：http://blog.csdn.net/sinat_23092639/article/details/51160621