双向循环链表

[java]代码库
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;
    }
}
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[java]代码库

网友评论 (发表评论)

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
