代碼如下:

package com.xlst.util;

import java.util.HashMap;

import java.util.Map;

import java.util.UUID;

/**

* 雙向循環(huán)鏈表

* 完成時(shí)間：2012.9.28

* 版本1.0

* @author xlst

*

*/

public class BothwayLoopLinked {

/**

* 存放鏈表長(zhǎng)度的 map

*

* 如果簡(jiǎn)單使用 static int 型的 size 基本類型變量，則只能維護(hù)一個(gè)雙向循環(huán)鏈表。

* 同時(shí)存在兩個(gè)及以上雙向循環(huán)鏈表時(shí)，數(shù)據(jù)會(huì)錯(cuò)亂

*/

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

/**

* 雙向鏈表的 id

* 一個(gè)雙向一個(gè)唯一的 id

* 根據(jù)這個(gè)id可以從 sizeMap 中取出當(dāng)前鏈表的長(zhǎng)度

*/

private String linkedId = null;

/**

* 節(jié)點(diǎn)中的數(shù)據(jù)

*/

private Object data = null;

/**

* 前一個(gè)節(jié)點(diǎn)（初始化時(shí)是自身）

*/

private BothwayLoopLinked prev = this;

/**

* 后一個(gè)節(jié)點(diǎn)（初始化時(shí)是自身）

*/

private BothwayLoopLinked next = this;

public BothwayLoopLinked(){}

/**

* 在節(jié)點(diǎn)之后插入新節(jié)點(diǎn)

* @param newLinked 新插入的節(jié)點(diǎn)

*/

public void insertAfter(BothwayLoopLinked newLinked){

// 原來的前節(jié)點(diǎn)與后節(jié)點(diǎn)

BothwayLoopLinked oldBefore = this;

BothwayLoopLinked oldAfter = this.next;

// 設(shè)置 newLinked 與原前節(jié)點(diǎn)的關(guān)系

oldBefore.next = newLinked;

newLinked.prev = oldBefore;

// 設(shè)置 newLinked 與原后節(jié)點(diǎn)的關(guān)系

oldAfter.prev = newLinked;

newLinked.next = oldAfter;

// 鏈表長(zhǎng)度加一

changeSize(+1);

// 綁定新節(jié)點(diǎn)的 linkedId

newLinked.linkedId = this.linkedId;

}

/**

* 在節(jié)點(diǎn)之前插入新節(jié)點(diǎn)

* @param newLinked 新插入的節(jié)點(diǎn)

*/

public void insertBefore(BothwayLoopLinked newLinked){

// 原來的前節(jié)點(diǎn)與后節(jié)點(diǎn)

BothwayLoopLinked oldBefore = this.prev;

BothwayLoopLinked oldAfter = this;

// 設(shè)置 newLinked 與原前節(jié)點(diǎn)的關(guān)系

oldBefore.next = newLinked;

newLinked.prev = oldBefore;

// 設(shè)置 newLinked 與原后節(jié)點(diǎn)的關(guān)系

oldAfter.prev = newLinked;

newLinked.next = oldAfter;

// 鏈表長(zhǎng)度加一

changeSize(+1);

// 綁定新節(jié)點(diǎn)的 linkedId

newLinked.linkedId = this.linkedId;

}

/**

* 從鏈表結(jié)構(gòu)中刪除自身

* @return 被刪除的節(jié)點(diǎn)

*/

public BothwayLoopLinked remove(){

return remove(this);

}

/**

* 從鏈表結(jié)構(gòu)中刪除指定節(jié)點(diǎn)

* @param linked 要?jiǎng)h除的節(jié)點(diǎn)

* @return 被刪除的節(jié)點(diǎn)

*/

public BothwayLoopLinked remove(BothwayLoopLinked linked){

linked.prev.next = linked.next;

linked.next.prev = linked.prev;

linked.prev = linked;

linked.next = linked;

// 鏈表長(zhǎng)度減一

changeSize(-1);

// 取消該節(jié)點(diǎn)的 linkedId

this.linkedId = null;

// 返回被刪除的節(jié)點(diǎn)

return linked;

}

/**

* 改變鏈表長(zhǎng)度（默認(rèn)長(zhǎng)度加1），私有方法

*/

private void changeSize(){

changeSize(1);

}

/**

* 改變鏈表長(zhǎng)度（根據(jù)參數(shù)），私有方法

* @param value 改變的長(zhǎng)度值（可以為負(fù)數(shù)）

*/

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;

}

/**

* 獲取鏈表的長(zhǎng)度

* 如果是新生的節(jié)點(diǎn) 或 從鏈表中刪除的節(jié)點(diǎn)，則作為獨(dú)立鏈表，長(zhǎng)度是 1

* @return 鏈表的長(zhǎng)度

*/

public int getSize() {

return (linkedId == null) ? 1 : sizeMap.get(this.linkedId);

}

public BothwayLoopLinked getPrev() {

return prev;

}

public BothwayLoopLinked getNext() {

return next;

}

}

例2

代碼如下:

/**

* 雙向循環(huán)鏈表測(cè)試

* @author GKT

* @param <E>

*/

public class Node<E>

{

private E element; //結(jié)點(diǎn)數(shù)據(jù)

private Node<E> next; //上結(jié)點(diǎn)

private Node<E> previous; //下結(jié)點(diǎn)

private static int size=0; //鏈表長(zhǎng)

//默認(rèn)關(guān)結(jié)點(diǎn)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)

{

//定義新結(jié)點(diǎn)，next-->頭結(jié)點(diǎn)；previous-->頭結(jié)點(diǎn).previous（尾結(jié)點(diǎn)）

Node<E> newNode=new Node<E>(e,this,this.previous==null?this:this.previous);

//頭結(jié)點(diǎn)next為空則讓它指向newNode

if(this.next==null)

{

this.next=newNode;

}

//頭結(jié)點(diǎn)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個(gè)元素

* @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個(gè)元素

* @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) );

}

}

這兩個(gè)鏈表最大的不同就是頭結(jié)點(diǎn)是否是啞元，以及取出元素(get函數(shù))的時(shí)候for循環(huán)變量i的不同：

雙向循環(huán)鏈表(和java.util包的設(shè)計(jì)一樣)：由于head是啞元，因此取元素從head的下一個(gè)結(jié)點(diǎn)取

單向鏈表：head不是啞元，第一次必須取head頭結(jié)點(diǎn)的元素，因此循環(huán)上和雙向循環(huán)鏈表不同。也就是第一次get并沒有進(jìn)入for循環(huán)，直接返回了頭結(jié)點(diǎn)，從第二次才開始進(jìn)入for循環(huán)，這里要特別注意

更多信息請(qǐng)查看IT技術(shù)專欄