java双向循环链表实现程序

　　例1

package com.xlst.util;

import java.util.HashMap;
import java.util.Map;
import java.util.UUID;


public class BothwayLooplinked {

private static final Map<String, Integer> sizeMap = new HashMap<String, Integer>();

private String linkedId = null;


private Object data = null;


private BothwayLooplinked prev = this;

private BothwayLooplinked next = this;

public BothwayLooplinked(){}


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;
}


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;
}


public BothwayLooplinked remove(){
return remove(this);
}

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;
}


private void changeSize(){
changeSize(1);
}

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;
}


public int getSize() {
return (linkedId == null) ? 1 : sizeMap.get(this.linkedId);
}

public BothwayLooplinked getPrev() {
return prev;
}

public BothwayLooplinked getNext() {
return next;
}
}

　　例2

public class Node<E>
{
private E element; //结点数据
private Node<E> next; //上结点
private Node<E> previous; //下结点
private static int size=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;
}

public void addAfter(E e)
{
//定义新结点，next-->头结点；previous-->头结点.previous（尾结点）
Node<E> newNode=new Node<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++;
}

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++;
}

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<E> temp=this;
for(int i=size;i>index;i--)
{
temp=temp.previous;
}
Node<E> newNode=new Node<E>(e,temp,temp.previous);
temp.previous.next=newNode;
temp.previous=newNode;
}
else
{
Node<E> temp=this;
for(int i=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++;
}
}

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<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--;
}
}

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<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 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循环，这里要特别注意