java 双向循环链表
博客园第一篇正式文章，献上自己的原创代码，欢迎园友交流指教！
java 之 双向循环链表 新鲜出炉
1 package com.xlst.util; 2 3 import java.util.HashMap; 4 import java.util.Map; 5 import java.util.UUID; 6 7 /** 8 * 双向循环链表 9 * 完成时间：2012.9.28 10 * 版本1.0 11 * @author xlst 12 * 13 */ 14 public class BothwayLoopLinked { 15 /** 16 * 存放链表长度的 map 17 * 18 * 如果简单使用 static int 型的 size 基本类型变量，则只能维护一个双向循环链表。 19 * 同时存在两个及以上双向循环链表时，数据会错乱 20 */ 21 private static final Map<String, Integer> sizeMap = new HashMap<String, Integer>(); 22 /** 23 * 双向链表的 id 24 * 一个双向一个唯一的 id 25 * 根据这个id可以从 sizeMap 中取出当前链表的长度 26 */ 27 private String linkedId = null; 28 29 /** 30 * 节点中的数据 31 */ 32 private Object data = null; 33 34 /** 35 * 前一个节点（初始化时是自身） 36 */ 37 private BothwayLoopLinked prev = this; 38 /** 39 * 后一个节点（初始化时是自身） 40 */ 41 private BothwayLoopLinked next = this; 42 43 public BothwayLoopLinked(){} 44 45 /** 46 * 在节点之后插入新节点 47 * @param newLinked 新插入的节点 48 */ 49 public void insertAfter(BothwayLoopLinked newLinked){ 50 // 原来的前节点与后节点 51 BothwayLoopLinked oldBefore = this; 52 BothwayLoopLinked oldAfter = this.next; 53 54 // 设置 newLinked 与原前节点的关系 55 oldBefore.next = newLinked; 56 newLinked.prev = oldBefore; 57 58 // 设置 newLinked 与原后节点的关系 59 oldAfter.prev = newLinked; 60 newLinked.next = oldAfter; 61 62 // 链表长度加一 63 changeSize(+1); 64 // 绑定新节点的 linkedId 65 newLinked.linkedId = this.linkedId; 66 } 67 68 /** 69 * 在节点之前插入新节点 70 * @param newLinked 新插入的节点 71 */ 72 public void insertBefore(BothwayLoopLinked newLinked){ 73 // 原来的前节点与后节点 74 BothwayLoopLinked oldBefore = this.prev; 75 BothwayLoopLinked oldAfter = this; 76 77 // 设置 newLinked 与原前节点的关系 78 oldBefore.next = newLinked; 79 newLinked.prev = oldBefore; 80 81 // 设置 newLinked 与原后节点的关系 82 oldAfter.prev = newLinked; 83 newLinked.next = oldAfter; 84 85 // 链表长度加一 86 changeSize(+1); 87 // 绑定新节点的 linkedId 88 newLinked.linkedId = this.linkedId; 89 } 90 91 /** 92 * 从链表结构中删除自身 93 * @return 被删除的节点 94 */ 95 public BothwayLoopLinked remove(){ 96 return remove(this); 97 } 98 /** 99 * 从链表结构中删除指定节点100 * @param linked 要删除的节点101 * @return 被删除的节点102 */103 public BothwayLoopLinked remove(BothwayLoopLinked linked){104 linked.prev.next = linked.next;105 linked.next.prev = linked.prev;106 107 linked.prev = linked;108 linked.next = linked;109 110 // 链表长度减一111 changeSize(-1);112 // 取消该节点的 linkedId113 this.linkedId = null;114 115 // 返回被删除的节点116 return linked;117 }118 119 /**120 * 改变链表长度（默认长度加1），私有方法121 */122 private void changeSize(){123 changeSize(1);124 }125 /**126 * 改变链表长度（根据参数），私有方法127 * @param value 改变的长度值（可以为负数）128 */129 private void changeSize(int value){130 if(this.linkedId == null){131 this.linkedId = UUID.randomUUID().toString();132 133 sizeMap.put(linkedId, 1 + value); // sizeMap.put(linkedId, 2);134 }else{135 Integer size = sizeMap.get(this.linkedId);136 // Integer 是引用类型，更新值之后不必再 put 回 sizeMap 里137 size += value;138 }139 }140 141 public Object getData() {142 return data;143 }144 145 public void setData(Object data) {146 this.data = data;147 }148 149 /**150 * 获取链表的长度151 * 如果是新生的节点 或 从链表中删除的节点，则作为独立链表，长度是 1152 * @return 链表的长度153 */154 public int getSize() {155 return (linkedId == null) ? 1 : sizeMap.get(this.linkedId);156 }157 158 public BothwayLoopLinked getPrev() {159 return prev;160 }161 162 public BothwayLoopLinked getNext() {163 return next;164 }165 }TAG:
