Code666 (代码贴、代码片段)

[Java] 双向循环链表 →→→→→进入此内容的聊天室

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

回复 "双向循环链表"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666