代碼如下
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<String, Integer> sizeMap = new HashMap<String, Integer>();
/**
* 雙向鏈表的 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 <E>
*/
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;
}
/**
* 尾部添加元素 e
* @param e
*/
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++;
}
/**
* 頭部添加元素 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 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++;
}
}
/**
* 刪除第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<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 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循環，這裡要特別注意
