java双向循环链表实现程序_编程语言综合--HTML5中文学习网

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