代码如下
packagecom.xlst.util;
import java.util.HashMap;
importjava.util.Map;
import java.util.UUID;
/**
* 双向循环链表
*完成时间:2012.9.28
* 版本1.0
* @author xlst
*
*/
public classBothwayLoopLinked {
/**
* 存放链表长度的 map
*
* 如果简单使用 static int 型的 size基本类型变量,则只能维护一个双向循环链表。
* 同时存在两个及以上双向循环链表时,数据会错乱
*/
private static final Map<String, Integer> sizeMap = new HashMap<String,Integer>();
/**
* 双向链表的 id
* 一个双向一个唯一的 id
* 根据这个id可以从 sizeMap 中取出当前链表的长度
*/
private String linkedId =null;
/**
*节点中的数据
*/
private Object data = null;
/**
*前一个节点(初始化时是自身)
*/
private BothwayLoopLinked prev =this;
/**
* 后一个节点(初始化时是自身)
*/
privateBothwayLoopLinked next = this;
publicBothwayLoopLinked(){}
/**
* 在节点之后插入新节点
* @param newLinked 新插入的节点
*/
public void insertAfter(BothwayLoopLinked newLinked){
//原来的前节点与后节点
BothwayLoopLinked oldBefore = this;
BothwayLoopLinked oldAfter = this.next;
//设置 newLinked与原前节点的关系
oldBefore.next = newLinked;
newLinked.prev =oldBefore;
//设置 newLinked 与原后节点的关系
oldAfter.prev = newLinked;
newLinked.next = oldAfter;
//链表长度加一
changeSize(+1);
//绑定新节点的 linkedId
newLinked.linkedId= this.linkedId;
}
/**
* 在节点之前插入新节点
* @param newLinked 新插入的节点
*/
public voidinsertBefore(BothwayLoopLinked newLinked){
//原来的前节点与后节点
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= this.linkedId;
}
/**
* 从链表结构中删除自身
* @return 被删除的节点
*/
public BothwayLoopLinkedremove(){
return remove(this);
}
/**
*从链表结构中删除指定节点
* @param linked 要删除的节点
* @return 被删除的节点
*/
public BothwayLoopLinked remove(BothwayLoopLinkedlinked){
linked.prev.next = linked.next;
linked.next.prev = linked.prev;
linked.prev =linked;
linked.next = linked;
//链表长度减一
changeSize(-1);
//取消该节点的 linkedId
this.linkedId =null;
//返回被删除的节点
return linked;
}
/**
*改变链表长度(默认长度加1),私有方法
*/
private void changeSize(){
changeSize(1);
}
/**
* 改变链表长度(根据参数),私有方法
*@param value 改变的长度值(可以为负数)
*/
private void changeSize(intvalue){
if(this.linkedId == 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() {
returndata;
}
public void setData(Object data) {
this.data = data;
}
/**
* 获取链表的长度
*如果是新生的节点 或 从链表中删除的节点,则作为独立链表,长度是 1
* @return 链表的长度
*/
public int getSize() {
return (linkedId == null) ? 1 :sizeMap.get(this.linkedId);
}
public BothwayLoopLinkedgetPrev() {
return prev;
}
publicBothwayLoopLinked getNext() {
return next;
}
}
例2
代码如下
/**
*双向循环链表测试
* @author GKT
* @param <E>
*/
public classNode<E>
{
private Eelement;//结点数据
private Node<E> next;//上结点
private Node<E> previous;//下结点
private static intsize=0;//链表长
//默认关结点next previous都是空,
public Node()
{
this.element=null;
this.next=null;
this.previous=null;
}
private Node(E element,Node<E>next,Node<E> previous)
{
this.element=element;
this.next=next;
this.previous=previous;
}
/**
* 尾部添加元素 e
* @param e
*/
public voidaddAfter(E e)
{
//定义新结点,next-->头结点;previous-->头结点.previous(尾结点)
Node<E>newNode=newNode<E>(e,this,this.previous==null?this:this.previous);
//头结点next为空则让它指向newNode
if(this.next==null)
{
this.next=newNode;
}
//头结点previous为空则让它指向newNode
if(this.previous==null)
{
this.previous=newNode;
}
this.previous.next=newNode;
this.previous=newNode;
size++;
}
/**
* 头部添加元素 e
* @param e
*/
public void addBefor(E e)
{
Node<E>newNode=new Node<E>(e,this.next==null?this:this.next,this);
if(this.next==null)
{
this.next=newNode;
}
if(this.previous==null)
{
this.previous=newNode;
}
this.next.previous=newNode;
this.next=newNode;
size++;
}
/**
* 在index处添加元素e
* @param e
*@param index
*/
public void add(E e,int index)
{
//索引越界
if(index>=size || index<0)
{
throw newIndexOutOfBoundsException("Node.get():"+index);
}
else
{
//index>size/2,反向遍历
if(index>size>>1)
{
Node<E>temp=this;
for(int i=size;i>index;i--)
{
temp=temp.previous;
}
Node<E> newNode=newNode<E>(e,temp,temp.previous);
temp.previous.next=newNode;
temp.previous=newNode;
}
else
{
Node<E> temp=this;
for(inti=0;i<=index;i++)
{
temp=temp.next;
}
Node<E>newNode=new Node<E>(e,temp,temp.previous);
temp.previous.next=newNode;
temp.previous=newNode;
}
size++;
}
}
/**
* 删除第index个元素
* @param index
*/
public void remove(int index)
{
//索引越界
if(index>=size || index<0)
{
throw newIndexOutOfBoundsException("Node.get():"+index);
}
else
{
//index>size/2,反向遍历
if(index>size>>1)
{
Node<E>temp=this;
for(int i=size;i>index;i--)
{
temp=temp.previous;
}
temp.previous.next=temp.next;
temp.next.previous=temp.previous;
}
else
{
Node<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 || index<0)
{
throw newIndexOutOfBoundsException("Node.get():"+index);
}
else
{
//index>size/2,反向遍历
if(index>size>>1)
{
Node<E>temp=this;
for(int i=size;i>index;i--)
{
temp=temp.previous;
}
return temp.element;
}
else
{
Node<E>temp=this;
for(int i=0;i<=index;i++)
{
temp=temp.next;
}
return temp.element;
}
}
}
public intsize()
{
return size;
}
public static void main(Stringa[])
{
Node node=new Node();
node.addAfter("1");
node.addAfter("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循环,这里要特别注意