双向循环链表

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