正文
前文介绍了java基础-链表
双向循环链表就是链表的升级版，多了有头，尾指针之分，指针的方向是双向的！！！
首先创一个节点类：
package cn.itcast.huahai.linklist; //AnyType表示任意类型 public class DulNode<AnyType>{ public AnyType data;//数值 public DulNode<AnyType> next;//前驱节点 public DulNode<AnyType> prior;//后继节点 //初始化 public DulNode() { this(null); } public DulNode(AnyType data) { this.data=data; this.prior=null; this.next=null; } }
创建一个接口类：
package cn.itcast.huahai.linklist; /* * 双向循环链表 */ public interface IList<AnyType> { public void addDulNode(AnyType x)throws Exception;//添加元素的方法 public void removeDulNode(int i)throws Exception;//移出元素的方法 public AnyType getDulNode(int i)throws Exception;//获取元素的方法 public int indexOfDulNode(AnyType x);//查找元素的方法 public void clearDulNode();//置空元素的方法 public boolean isEmptyDulNode();//判断空元素的方法 public void displayDulNode();//打印元素的方法 public int length();//元素长度的方法 }
实现接口的所有方法：
package cn.itcast.huahai.linklist; public class DulLinkList<AnyType> implements IList<AnyType>{ public DulNode<AnyType> beginMarker;//头指针 public DulNode<AnyType> endMarker;//尾指针 //初始化 public DulLinkList() { beginMarker=new DulNode<AnyType>(); endMarker=new DulNode<AnyType>(); beginMarker.prior=endMarker; beginMarker.next=null; endMarker.prior=null; endMarker.next=beginMarker; } public void addDulNode(AnyType x) throws Exception { DulNode<AnyType> node=new DulNode<AnyType>(x); if(beginMarker.next==null) { beginMarker.next=node; node.prior=beginMarker; }else { endMarker.next=node; node.prior=endMarker; } endMarker=node; endMarker.next=beginMarker; beginMarker.prior=endMarker; } public void removeDulNode(int i) throws Exception { DulNode<AnyType> p=beginMarker.next; int j=0; while(!beginMarker.equals(p)&&j<i) { j++; p=p.next; } p.prior.next=p.next; p.next.prior=p.prior; } public AnyType getDulNode(int i) throws Exception { DulNode<AnyType> p=beginMarker.next; int j=0; while(!beginMarker.equals(p)&&j<i) { j++; p=p.next; } return p.data; } public int indexOfDulNode(AnyType x) { DulNode<AnyType> p=beginMarker.next; int j=0; while(!beginMarker.equals(p)&&!x.equals(p.data)) { j++; p=p.next; } if(!beginMarker.equals(p)) return j; else return -1; } public void clearDulNode() { beginMarker.next=null; endMarker.prior=null; } public int length() { DulNode<AnyType> p=beginMarker.next; int length=0; while(!beginMarker.equals(p)) { length++; p=p.next; } return length; } public boolean isEmptyDulNode() { return beginMarker.next==null; } public void displayDulNode() { DulNode<AnyType> p=beginMarker.next; while(!beginMarker.equals(p)){ System.out.print(p.data+" "); p=p.next; } System.out.println(); } public static void main(String[] args) throws Exception { long begintime=System.currentTimeMillis(); Thread.currentThread(); Thread.sleep(1);//睡眠1毫秒 DulLinkList<Object> L=new DulLinkList<Object>(); for (int i = 0; i < 10; i++) { L.addDulNode(i);//插入元素 } long endtime=System.currentTimeMillis(); //L.clearDulNode();//置空元素 if(L.isEmptyDulNode()){ System.out.println("非常抱歉,链表为空."); System.out.println("耗时："+(endtime-begintime-1)+"毫秒."); }else{ System.out.print("双向循坏链表:"); L.displayDulNode(); System.out.println("双向循坏链表的元素长度："+L.length());//元素长度 System.out.println("双向循坏链表移出的元素：0");//移出元素 L.removeDulNode(0); System.out.print("双向循坏链表:"); L.displayDulNode(); System.out.println("双向循坏链表的元素长度："+L.length());//元素长度 System.out.println("双向循坏链表的元素为'1'的索引："+L.indexOfDulNode(1));//查找元素 System.out.println("双向循坏链表的索引为1的元素："+L.getDulNode(1)); System.out.println("耗时："+(endtime-begintime-1)+"毫秒.");//消耗时间 } } }
运行结果：
