java 双向循环链表

博客园第一篇正式文章，献上自己的原创代码，欢迎园友交流指教！

java 之 双向循环链表 新鲜出炉

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