例1

代码如下:

package com.xlst.util;

import java.util.HashMap;

import java.util.Map;

import java.util.UUID;

/**

* 双向循环链表

* 完成时间：2012.9.28

* 版本1.0

* @author xlst

*

*/

public class BothwayLoopLinked {

/**

* 存放链表长度的 map

*

* 如果简单使用 static int 型的 size 基本类型变量，则只能维护一个双向循环链表。

* 同时存在两个及以上双向循环链表时，数据会错乱

*/

private static final Map sizeMap = new HashMap();

/**

* 双向链表的 id

* 一个双向一个唯一的 id

* 根据这个id可以从 sizeMap 中取出当前链表的长度

*/

private String linkedId = null;

/**

* 节点中的数据

*/

private Object data = null;

/**

* 前一个节点（初始化时是自身）

*/

private BothwayLoopLinked prev = this;

/**

* 后一个节点（初始化时是自身）

*/

private BothwayLoopLinked next = this;

public BothwayLoopLinked(){}

/**

* 在节点之后插入新节点

* @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 void insertBefore(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 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 = 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 == 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 = 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

*/

public class Node

{

private E element; //结点数据

private Node next; //上结点

private Node previous; //下结点

private static int size=0; //链表长

//默认关结点next previous都是空，

public Node()

{

this.element=null;

this.next=null;

this.previous=null;

}

private Node(E element,Node next,Node previous)

{

this.element=element;

this.next=next;

this.previous=previous;

}

/**

* 尾部添加元素 e

* @param e

*/

public void addAfter(E e)

{

//定义新结点，next-->头结点；previous-->头结点.previous（尾结点）

Node newNode=new Node(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 newNode=new Node(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 new IndexOutOfBoundsException("Node.get():"+index);

}

else

{

//index>size/2,反向遍历

if(index>size>>1)

{

Node temp=this;

for(int i=size;i>index;i--)

{

temp=temp.previous;

}

Node newNode=new Node(e,temp,temp.previous);

temp.previous.next=newNode;

temp.previous=newNode;

}

else

{

Node temp=this;

for(int i=0;i<=index;i++)

{

temp=temp.next;

}

Node newNode=new Node(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 new IndexOutOfBoundsException("Node.get():"+index);

}

else

{

//index>size/2,反向遍历

if(index>size>>1)

{

Node temp=this;

for(int i=size;i>index;i--)

{

temp=temp.previous;

}

temp.previous.next=temp.next;

temp.next.previous=temp.previous;

}

else

{

Node 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 new IndexOutOfBoundsException("Node.get():"+index);

}

else

{

//index>size/2,反向遍历

if(index>size>>1)

{

Node temp=this;

for(int i=size;i>index;i--)

{

temp=temp.previous;

}

return temp.element;

}

else

{

Node 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("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技术专栏