达内LOGO和北京达内网址达内科技培训项目:Java培训 3G培训 Android培训 软件测试培训北京达内服务电话
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 = http://www.cnblogs.com/xlst/archive/2012/09/28/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 =http://www.cnblogs.com/xlst/archive/2012/09/28/ 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 }