【JDK学习篇】LinkedList模仿_josh bloch

java中LinkedList的实现,看看Josh Bloch写的源码才发现真正大师的作品，真的是佩服的五体投地

如图就是josh Bloch，自己还买过他的《Efficient java》，不过至今还躺在自己的书架上。
这次看看jdk中的源码从中学习，发现他们写的东西真的注意到很多，不论是安全，还是快捷方面都是自己要学习的。

模仿心得体会

• 在学习源码时，便对着高淇的java300集学，然后就是打开源码自己模仿，在编写过程中也出现过许多错误，然后就是对着他的源码抄，看看他的设计的方法，他的怎么实现。关于代码复用源码做到的很详细，把一些小的功能拧出来。使代码更加简洁有力，内聚性很强，耦合度低。
• 在获取指定位置结点时，josh Bloch根据index < (size >> 1)判断，从而缩小范围，更加迅速。

josh Bloch代码使用泛型，内部Node类内实现数据更好的隐藏，如：

仔细一看才发现大师写的那才是艺术，给人美的享受。
记得曾经读过的一片文章写到好的代码就是读的时候骂娘的次数，读JDK源码我真的是很折服，完全被它的代码所吸引。

不足之处

没有使用泛型，和内部类。另外还有一些细节还没有全部展开
比如源码中的transient、Serializable（串行化）还没有用上。

package com.huat.container;

import java.util.List;

class Node {
    private Node front;
    private Object obj;
    private Node next;

    public Node() {

    }

    public Node getFront() {
    return front;
    }

    public Node(Node front, Object obj, Node next) {
    super();
    this.front = front;
    this.obj = obj;
    this.next = next;
    }

    public void setFront(Node front) {
    this.front = front;
    }

    public Object getObj() {
    return obj;
    }

    public void setObj(Object obj) {
    this.obj = obj;
    }

    public Node getNext() {
    return next;
    }

    public void setNext(Node next) {
    this.next = next;
    }

}

public class ArrayList {

    /*********************************************
     * LinkList java实现双向链表
     * 
     **********************************************/
    private Node first;
    private Node last;
    private int size;

    /**
     * node结点插入数据
     */
    public void add(Object obj) {

    Node node = new Node(null,obj,null);

    if (first == null) {
        first = node;
        last = node;
    } else {
        last.setNext(node);
        node.setFront(last);
        last = node;
    }
    size++;
    }

    public int getSize() {
    return size;
    }

    private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
    }

    private String outBoundsMsg(int index) {
    return "index " + index + ", size " + size;
    }

    private void checkElementIndex(int index) {
    // 如果下标越界则抛出异常
    if (!isElementIndex(index)) {
        throw new IndexOutOfBoundsException(outBoundsMsg(index));
    }
    }

    private Node node(int index) {
    // 使用二分查找
    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++) {
        x = x.getNext();
        }
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--) {
        x = x.getFront();
        }
        return x;
    }
    }

    public Object get(int index) {
    // 检查合法性
    checkElementIndex(index);
    return node(index).getObj();
    }

    public Object unlink(Node n) {
    Object o = n.getObj();
    Node front = n.getFront();
    Node next = n.getNext();

    if (front == null) {
        first = next;
    } else {
        front.setNext(next);
        n.setFront(null);       //释放n结点的前驱
    }

    if (next == null) {
        last = front;
    } else {
        next.setFront(front);
        n.setNext(null);        //释放n结点的后继结点
    }
    n.setObj(null);
    size--;
    return o;
    }

    public Object remove(int index) {
    checkElementIndex(index);
    Object o = unlink(node(index));
    return o;
    }

    public boolean remove(Object o) {
    // 从起始位置遍历链表，如果找到第一个相同的obj就直接删除
    Node temp = first;
    if (o == null) {
        while (temp.getNext() != null) {
        if (temp.getObj() == null) {
            unlink(temp);
            return true;
        }
        temp = temp.getNext();
        }
    } else {
        while (temp.getNext() != null) {
        if (o.equals(temp.getObj())) {
            unlink(temp);
            return true;
        }
        temp = temp.getNext();
        }
    }
    return false;
    }

    private void linkLast(Object o) {
    Node l = last;
    Node n = new Node(l,o,null);
    if (l == null) {
        last = n;
    } else {
        l.setNext(n);
    }
    size++;
    }

    private void linkBefore(Object o,Node point) {
    Node prev = point.getFront();
    Node newNode = new Node(prev, o, point);
    point.setFront(newNode);    
    if (prev == null) {
        first = newNode;
    } else {
        prev.setNext(newNode);
    }
    size++;
    }

    public void add(int index, Object o) {
    if (index > size) {
        throw new IndexOutOfBoundsException("index " + index + "超出 size " + size);
    }

    if (index == size) {
        linkLast(o);
    } else {
        linkBefore(o, node(index));
    }

    }

    public void print() {
    Node temp = first;
    do {
        System.out.print(temp.getObj() + " ");
        temp = temp.getNext();
    } while (temp != null);

    }

    public static void main(String[] args) {
    ArrayList list = new ArrayList();
    list.add("aa");
    list.add("bb");
    list.add("cc");
    list.add("bb");
    list.add("dd");

    list.add(5,"ee");

    // Test
    System.out.println("链表中的值为 :");
    list.print();   //遍历链表
    System.out.println();

    System.out.println("移除制定对象后的链表");
    System.out.println(list.remove("aa"));  //移除制定位置元素
    list.print();

    System.out.println();
    System.out.println(list.getSize());     //获取链表大小
    System.out.println(list.get(2));    //获取特点位置元素
    System.out.println(list.remove(0)); //移除制定位置元素
    list.print();
    System.out.println(list.getSize());
    System.out.println(list.get(0));

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244

运行结果