《java双向循环链表实现程序__1.docx》由会员分享，可在线阅读，更多相关《java双向循环链表实现程序__1.docx（18页珍藏版）》请在三一文库上搜索。
1、java双向循环链表实现程序_例1 代码如下: package com.xlst.util; import java.util.HashMap; import java.util.Map; import java.util.UUID; /* * 双向循环链表 * 完成时间：2021.9.28 * 版本1.0 * author xlst * */ public class BothwayLoopLinked /* * 存放链表长度的 map * * 假如简洁用法 static int 型的 size 基本类型变量，则只能维护一个双向循环链表。 * 同时存在两个及以上双向循环链表时，数据会错乱 *
2、/ private static final MapString, Integer sizeMap = new HashMapString, Integer(); /* * 双向链表的 id * 一个双向一个唯一的 id * 依据这个id可以从 sizeMap 中取出当前链表的长度 */ private String linkedId = null; /* * 节点中的数据 */ private Object data = null; /* * 前一个节点（初始化时是自身） */ private BothwayLoopLinked prev = this; /* * 后一个节点（初始化时是自身
3、） */ private BothwayLoopLinked next = this; public BothwayLoopLinked() /* * 在节点之后插入新节点 * param newLinked 新插入的节点 */ public void insertAfter(BothwayLoopLinked newLinked) / 原来的前节点与后节点 BothwayLoopLinked oldBefore = this; BothwayLoopLinked oldAfter = this.next; / 设置 newLinked 与原前节点的关系 oldBefore.next = ne
4、wLinked; newLinked.prev = oldBefore; / 设置 newLinked 与原后节点的关系 oldAfter.prev = newLinked; newLinked.next = oldAfter; / 链表长度加一 changeSize(+1); / 绑定新节点的 linkedId newLinked.linkedId = this.linkedId; /* * 在节点之前插入新节点 * param newLinked 新插入的节点 */ public void insertBefore(BothwayLoopLinked newLinked) / 原来的前节点
5、与后节点 BothwayLoopLinked oldBefore = this.prev; BothwayLoopLinked oldAfter = this; / 设置 newLinked 与原前节点的关系 oldBefore.next = newLinked; newLinked.prev = oldBefore; / 设置 newLinked 与原后节点的关系 oldAfter.prev = newLinked; newLinked.next = oldAfter; / 链表长度加一 changeSize(+1); / 绑定新节点的 linkedId newLinked.linkedId
6、 = this.linkedId; /* * 从链表结构中删除自身 * return 被删除的节点 */ public BothwayLoopLinked remove() return remove(this); /* * 从链表结构中删除指定节点 * param linked 要删除的节点 * return 被删除的节点 */ public BothwayLoopLinked remove(BothwayLoopLinked linked) linked.prev.next = linked.next; linked.next.prev = linked.prev; linked.prev
7、 = linked; linked.next = linked; / 链表长度减一 changeSize(-1); / 取消该节点的 linkedId this.linkedId = null; / 返回被删除的节点 return linked; /* * 转变链表长度（默认长度加1），私有方法 */ private void changeSize() changeSize(1); /* * 转变链表长度（依据参数），私有方法 * param value 转变的长度值（可以为负数） */ private void changeSize(int value) if(this.linkedId =
8、 null) this.linkedId = UUID.randomUUID().toString(); sizeMap.put(linkedId, 1 + value); / sizeMap.put(linkedId, 2); else Integer size = sizeMap.get(this.linkedId); / Integer 是引用类型，更新值之后不必再 put 回 sizeMap 里 size += value; public Object getData() return data; public void setData(Object data) this.data =
9、 data; /* * 猎取链表的长度 * 假如是新生的节点 或 从链表中删除的节点，则作为独立链表，长度是 1 * return 链表的长度 */ public int getSize() return (linkedId = null) ? 1 : sizeMap.get(this.linkedId); public BothwayLoopLinked getPrev() return prev; public BothwayLoopLinked getNext() return next; 例2 代码如下: /* * 双向循环链表测试 * author GKT * param E */
10、public class NodeE private E element; /结点数据 private NodeE next; /上结点 private NodeE previous; /下结点 private static int size=0; /链表长 /默认关结点next previous都是空， public Node() this.element=null; this.next=null; this.previous=null; private Node(E element,NodeE next,NodeE previous) this.element=element; this.
11、next=next; this.previous=previous; /* * 尾部添加元素 e * param e */ public void addAfter(E e) /定义新结点，next-头结点；previous-头结点.previous（尾结点） NodeE newNode=new NodeE(e,this,this.previous=null?this:this.previous); /头结点next为空则让它指向newNode if(this.next=null) this.next=newNode; /头结点previous为空则让它指向newNode if(this.pr
12、evious=null) this.previous=newNode; this.previous.next=newNode; this.previous=newNode; size+; /* * 头部添加元素 e * param e */ public void addBefor(E e) NodeE newNode=new NodeE(e,this.next=null?this:this.next,this); if(this.next=null) this.next=newNode; if(this.previous=null) this.previous=newNode; this.n
13、ext.previous=newNode; this.next=newNode; size+; /* * 在index处添加元素e * param e * param index */ public void add(E e,int index) /索引越界 if(index=size | index0) throw new IndexOutOfBoundsException(Node.get():+index); else /indexsize/2,反向遍历 if(indexsize1) NodeE temp=this; for(int i=size;iindex;i-) temp=temp
14、.previous; NodeE newNode=new NodeE(e,temp,temp.previous); temp.previous.next=newNode; temp.previous=newNode; else NodeE temp=this; for(int i=0;i=index;i+) temp=temp.next; NodeE newNode=new NodeE(e,temp,temp.previous); temp.previous.next=newNode; temp.previous=newNode; size+; /* * 删除第index个元素 * param
15、 index */ public void remove(int index) /索引越界 if(index=size | index0) throw new IndexOutOfBoundsException(Node.get():+index); else /indexsize/2,反向遍历 if(indexsize1) NodeE temp=this; for(int i=size;iindex;i-) temp=temp.previous; temp.previous.next=temp.next; temp.next.previous=temp.previous; else Node
16、E temp=this; for(int i=0;i=index;i+) temp=temp.next; temp.previous.next=temp.next; temp.next.previous=temp.previous; size-; /* * 取得第index个元素 * param index * return */ public E get(int index) /索引越界 if(index=size | index0) throw new IndexOutOfBoundsException(Node.get():+index); else /indexsize/2,反向遍历
17、if(indexsize1) NodeE temp=this; for(int i=size;iindex;i-) temp=temp.previous; return temp.element; else NodeE temp=this; for(int i=0;i=index;i+) temp=temp.next; return temp.element; public int size() return size; public static void main(String a) Node node=new Node(); node.addAfter(1); node.addAfter
18、(2); node.addAfter(3); node.addBefor(0); node.add(7, 0); System.out.println(node.get(0) ); System.out.println(node.get(1) ); System.out.println(node.get(2) ); System.out.println(node.get(3) ); System.out.println(node.get(4) ); 这两个链表最大的不同就是头结点是否是哑元，以及取出元素(get函数)的时候for循环变量i的不同： 双向循环链表(和java.util包的设计一样)：由于head是哑元，因此取元素从head的下一个结点取 单向链表：head不是哑元，第一次必需取head头结点的元素，因此循环上和双向循环链表不同。也就是第一次get并没有进入for循环，挺直返回了头结点，从其次次才开头进入for循环，这里要格外留意 更多信息请查看IT技术专栏 .