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

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