双向循环链表

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