Code666 (代码贴、代码片段)

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

来自 , 2020-09-25, 写在 Java, 查看 121 次.
URL http://www.code666.cn/view/f2201f51
  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.         //    取消该节点的 linkedId
  113.         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.      * 如果是新生的节点 或 从链表中删除的节点，则作为独立链表，长度是 1
  152.      * @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. }

回复 "双向循环链表"

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

captcha

贴代码片段 - Code666