java雙向循環(huán)鏈表實(shí)現(xiàn)程序

例1
    代碼如下:
    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 基本類(lèi)型變量，則只能維護(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){
    // 原來(lái)的前節(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){
    // 原來(lái)的前節(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 是引用類(lèi)型，更新值之后不必再 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并沒(méi)有進(jìn)入for循環(huán)，直接返回了頭結(jié)點(diǎn)，從第二次才開(kāi)始進(jìn)入for循環(huán)，這里要特別注意