java集合源码解读：List集合（ArrayList、Vector、CopyOnWriteArrayList、LinkedList、Stack）1.ArrayList2.Vector3.CopyOnWriteArraryList4.LinkedList5.Stack

109 阅读 0 评论 72 点赞

我是靠谱客的博主重要冷风，这篇文章主要介绍java集合源码解读：List集合（ArrayList、Vector、CopyOnWriteArrayList、LinkedList、Stack）1.ArrayList2.Vector3.CopyOnWriteArraryList4.LinkedList5.Stack，现在分享给大家，希望可以做个参考。

1.ArrayList

复制代码

package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 序列版本号
    private static final long serialVersionUID = 8683452581122892189L;

// 保存ArrayList中数据的数组
    private transient Object[] elementData;

// ArrayList中实际数据的数量
    private int size;

// ArrayList带容量大小的构造函数。
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        // 新建一个数组
        this.elementData = new Object[initialCapacity];
    }

// ArrayList构造函数。默认容量是10。
    public ArrayList() {
        this(10);
    }

// 创建一个包含collection的ArrayList
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

// 将当前容量值设为 =实际元素个数
    public void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

// 确定ArrarList的容量。
    // 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”
    public void ensureCapacity(int minCapacity) {
        // 将“修改统计数”+1
        modCount++;
        int oldCapacity = elementData.length;
        // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

// 添加元素e
    public boolean add(E e) {
        // 确定ArrayList的容量大小
        ensureCapacity(size + 1);  // Increments modCount!!
        // 添加e到ArrayList中
        elementData[size++] = e;
        return true;
    }

// 返回ArrayList的实际大小
    public int size() {
        return size;
    }

// 返回ArrayList是否包含Object(o)
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

// 返回ArrayList是否为空
    public boolean isEmpty() {
        return size == 0;
    }

// 正向查找，返回元素的索引值
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
            } else {
                for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
            }
            return -1;
        }

// 反向查找，返回元素的索引值
        public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
        } else {
            for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
        }
        return -1;
    }

// 反向查找(从数组末尾向开始查找)，返回元素(o)的索引值
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
        } else {
            for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
        }
        return -1;
    }

// 返回ArrayList的Object数组
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

// 返回ArrayList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
    public <T> T[] toArray(T[] a) {
        // 若数组a的大小 < ArrayList的元素个数；
        // 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中
        if (a.length < size)
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());

// 若数组a的大小 >= ArrayList的元素个数；
        // 则将ArrayList的全部元素都拷贝到数组a中。
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

// 获取index位置的元素值
    public E get(int index) {
        RangeCheck(index);

return (E) elementData[index];
    }

// 设置index位置的值为element
    public E set(int index, E element) {
        RangeCheck(index);

E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

// 将e添加到ArrayList中
    public boolean add(E e) {
        ensureCapacity(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

// 将e添加到ArrayList的指定位置
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(
            "Index: "+index+", Size: "+size);

ensureCapacity(size+1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
             size - index);
        elementData[index] = element;
        size++;
    }

// 删除ArrayList指定位置的元素
    public E remove(int index) {
        RangeCheck(index);

modCount++;
        E oldValue = (E) elementData[index];

int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                 numMoved);
        elementData[--size] = null; // Let gc do its work

return oldValue;
    }

// 删除ArrayList的指定元素
    public boolean remove(Object o) {
        if (o == null) {
                for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
        } else {
            for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
        }
        return false;
    }

// 快速删除第index个元素
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        // 从"index+1"开始，用后面的元素替换前面的元素。
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最后一个元素设为null
        elementData[--size] = null; // Let gc do its work
    }

// 删除元素
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
            return true;
            }
        } else {
            // 便利ArrayList，找到“元素o”，则删除，并返回true。
            for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
            return true;
            }
        }
        return false;
    }

// 清空ArrayList，将全部的元素设为null
    public void clear() {
        modCount++;

for (int i = 0; i < size; i++)
            elementData[i] = null;

size = 0;
    }

// 将集合c追加到ArrayList中
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

// 从index位置开始，将集合c添加到ArrayList
    public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(
            "Index: " + index + ", Size: " + size);

Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(size + numNew);  // Increments modCount

int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                 numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

// 删除fromIndex到toIndex之间的全部元素。
    protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

// Let gc do its work
    int newSize = size - (toIndex-fromIndex);
    while (size != newSize)
        elementData[--size] = null;
    }

private void RangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(
        "Index: "+index+", Size: "+size);
    }

// 克隆函数
    public Object clone() {
        try {
            ArrayList<E> v = (ArrayList<E>) super.clone();
            // 将当前ArrayList的全部元素拷贝到v中
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }

// java.io.Serializable的写入函数
    // 将ArrayList的“容量，所有的元素值”都写入到输出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

// 写入“数组的容量”
        s.writeInt(elementData.length);

// 写入“数组的每一个元素”
    for (int i=0; i<size; i++)
            s.writeObject(elementData[i]);

if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

}

// java.io.Serializable的读取函数：根据写入方式读出
    // 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in size, and any hidden stuff
        s.defaultReadObject();

// 从输入流中读取ArrayList的“容量”
        int arrayLength = s.readInt();
        Object[] a = elementData = new Object[arrayLength];

// 从输入流中将“所有的元素值”读出
        for (int i=0; i<size; i++)
            a[i] = s.readObject();
    }
}

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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 序列版本号
    private static final long serialVersionUID = 8683452581122892189L;

    // 保存ArrayList中数据的数组
    private transient Object[] elementData;

    // ArrayList中实际数据的数量
    private int size;

    // ArrayList带容量大小的构造函数。
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        // 新建一个数组
        this.elementData = new Object[initialCapacity];
    }

    // ArrayList构造函数。默认容量是10。
    public ArrayList() {
        this(10);
    }

    // 创建一个包含collection的ArrayList
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }


    // 将当前容量值设为 =实际元素个数
    public void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }


    // 确定ArrarList的容量。
    // 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”
    public void ensureCapacity(int minCapacity) {
        // 将“修改统计数”+1
        modCount++;
        int oldCapacity = elementData.length;
        // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

    // 添加元素e
    public boolean add(E e) {
        // 确定ArrayList的容量大小
        ensureCapacity(size + 1);  // Increments modCount!!
        // 添加e到ArrayList中
        elementData[size++] = e;
        return true;
    }

    // 返回ArrayList的实际大小
    public int size() {
        return size;
    }

    // 返回ArrayList是否包含Object(o)
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    // 返回ArrayList是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 正向查找，返回元素的索引值
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
            } else {
                for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
            }
            return -1;
        }

        // 反向查找，返回元素的索引值
        public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
        } else {
            for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
        }
        return -1;
    }

    // 反向查找(从数组末尾向开始查找)，返回元素(o)的索引值
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
        } else {
            for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
        }
        return -1;
    }
 

    // 返回ArrayList的Object数组
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    // 返回ArrayList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
    public <T> T[] toArray(T[] a) {
        // 若数组a的大小 < ArrayList的元素个数；
        // 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中
        if (a.length < size)
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());

        // 若数组a的大小 >= ArrayList的元素个数；
        // 则将ArrayList的全部元素都拷贝到数组a中。
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    // 获取index位置的元素值
    public E get(int index) {
        RangeCheck(index);

        return (E) elementData[index];
    }

    // 设置index位置的值为element
    public E set(int index, E element) {
        RangeCheck(index);

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

    // 将e添加到ArrayList中
    public boolean add(E e) {
        ensureCapacity(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    // 将e添加到ArrayList的指定位置
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(
            "Index: "+index+", Size: "+size);

        ensureCapacity(size+1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
             size - index);
        elementData[index] = element;
        size++;
    }

    // 删除ArrayList指定位置的元素
    public E remove(int index) {
        RangeCheck(index);

        modCount++;
        E oldValue = (E) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                 numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
    }

    // 删除ArrayList的指定元素
    public boolean remove(Object o) {
        if (o == null) {
                for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
        } else {
            for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
        }
        return false;
    }


    // 快速删除第index个元素
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        // 从"index+1"开始，用后面的元素替换前面的元素。
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最后一个元素设为null
        elementData[--size] = null; // Let gc do its work
    }

    // 删除元素
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
            return true;
            }
        } else {
            // 便利ArrayList，找到“元素o”，则删除，并返回true。
            for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
            return true;
            }
        }
        return false;
    }

    // 清空ArrayList，将全部的元素设为null
    public void clear() {
        modCount++;

        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    // 将集合c追加到ArrayList中
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    // 从index位置开始，将集合c添加到ArrayList
    public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(
            "Index: " + index + ", Size: " + size);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacity(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                 numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    // 删除fromIndex到toIndex之间的全部元素。
    protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

    // Let gc do its work
    int newSize = size - (toIndex-fromIndex);
    while (size != newSize)
        elementData[--size] = null;
    }

    private void RangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(
        "Index: "+index+", Size: "+size);
    }


    // 克隆函数
    public Object clone() {
        try {
            ArrayList<E> v = (ArrayList<E>) super.clone();
            // 将当前ArrayList的全部元素拷贝到v中
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }


    // java.io.Serializable的写入函数
    // 将ArrayList的“容量，所有的元素值”都写入到输出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

        // 写入“数组的容量”
        s.writeInt(elementData.length);

    // 写入“数组的每一个元素”
    for (int i=0; i<size; i++)
            s.writeObject(elementData[i]);

    if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

    }


    // java.io.Serializable的读取函数：根据写入方式读出
    // 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // 从输入流中读取ArrayList的“容量”
        int arrayLength = s.readInt();
        Object[] a = elementData = new Object[arrayLength];

        // 从输入流中将“所有的元素值”读出
        for (int i=0; i<size; i++)
            a[i] = s.readObject();
    }
}

(1) 底层数组

复制代码

1
2
 private transient Object[] elementData;//elementData是真正的保存数据的数组

transient，意为短暂的，瞬时的。

java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。只会在调用者的内存中使用，不会写入到磁盘中。如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。

（2）三种构造函数

ArrayList()：默认构造函数，提供初始容量为 10 的空列表。

ArrayList(int initialCapacity)：构造一个具有指定初始容量的空列表。

ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

复制代码

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
/**
 * 构造一个初始容量为 10 的空列表
 */
public ArrayList() {
    this(10);
}

/**
 * 构造一个具有指定初始容量的空列表。
 */
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
       throw new IllegalArgumentException("Illegal Capacity: "
                + initialCapacity);
    this.elementData = new Object [initialCapacity];
}

/**
 *  构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

(3)新增数据
ArrayList 提供了 add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)、set(int index, E element) 这个五个方法来实现 ArrayList 增加。

add(E e)：将指定的元素添加到此列表的尾部。

复制代码

1
2
3
4
5
6
public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments  modCount!!
	elementData[size++] = e;
	return true;
}

这里 ensureCapacity() 方法是对 ArrayList 集合进行扩容操作，elementData(size++) = e，将列表末尾元素指向e。

add(int index, E element)：将指定的元素插入此列表中的指定位置。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void add(int index, E element) {
  //判断索引位置是否正确
  if (index > size || index < 0)
      throw new IndexOutOfBoundsException(
      "Index: "+index+", Size: "+size);
  //扩容检测
  ensureCapacity(size+1);  
  /*
   * 对源数组进行复制处理（位移），从index + 1到size-index。
   * 主要目的就是空出index位置供数据插入，
   * 即向右移动当前位于该位置的元素以及所有后续元素。 
   */
  System.arraycopy(elementData, index,  elementData, index + 1,
           size - index);
  //在指定位置赋值
  elementData[index] = element;
  size++;
 }

在这个方法中最根本的方法就是 System.arraycopy() 方法，该方法的根本目的就是将 index 位置空出来以供新数据插入，这里需要进行数组数据的右移，这是非常麻烦和耗时的，所以如果指定的数据集合需要进行大量插入（中间插入）操作，推荐使用 LinkedList。

其他的新增方法也类似，都是先检测扩容，然后数组的复制，最后size++

（4）删除
ArrayList 提供了 remove(int index)、remove(Object o)、removeRange(int fromIndex, int toIndex)、removeAll() 四个方法进行元素的删除。

remove(int index)：移除此列表中指定位置上的元素。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E remove(int index) {
    //位置验证
    RangeCheck(index);

   modCount++;
   //需要删除的元素
    E oldValue = (E) elementData[index];   
    //向左移的位数
    int numMoved = size - index - 1;
    //若需要移动，则想左移动numMoved位
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    //置空最后一个元素
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

(5)查找

复制代码

1
2
3
4
5
6
public E get(int index) {
 	RangeCheck(index);

    return (E) elementData[index];
}

(6)扩容

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void ensureCapacity(int minCapacity) {
 	//修改计时器
    modCount++;
    //ArrayList容量大小
    int oldCapacity = elementData.length;
    /*
     * 若当前需要的长度大于当前数组的长度时，进行扩容操 作
     */
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        //计算新的容量大小，为当前容量的1.5倍
        int newCapacity = (oldCapacity * 3) / 2 + 1;
        if (newCapacity < minCapacity)
        newCapacity = minCapacity;
        //数组拷贝，生成新的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

扩容计算:(oldCapacity * 3) / 2 + 1;

2.Vector

(1)储存结构

复制代码

1
2
3
4
5
6
protected Object[] elementData;

protected int elementCount;

protected int capacityIncrement;

(2)vector的构造函数

复制代码

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
/**
 * 构造一个空向量，使其内部数据数组的大小为 10，其标准容量增量为零。
 */
 public Vector() {
        this(10);
 }

/**
 * 构造一个包含指定 collection 中的元素的向量，这些元素按其 collection 的迭代器返回元素的顺序排列。
 */
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount,
                Object[].class);
}

/**
 * 使用指定的初始容量和等于零的容量增量构造一个空向量。
 */
 public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

/**
 *  使用指定的初始容量和容量增量构造一个空的向量。
 */
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                          initialCapacity);
    this.elementData = new Object [initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

elementData ：”Object[] 类型的数组”，它保存了 Vector 中的元素。按照 Vector 的设计 elementData 为一个动态数组，可以随着元素的增加而动态的增长，其具体的增加方式后面提到（ensureCapacity 方法）。如果在初始化 Vector 时没有指定容器大小，则使用默认大小为 10.

elementCount：Vector 对象中的有效组件数。

capacityIncrement：向量的大小大于其容量时，容量自动增加的量。如果在创建 Vector 时，指定了 capacityIncrement 的大小；则，每次当 Vector 中动态数组容量增加时>，增加的大小都是 capacityIncrement。如果容量的增量小于等于零，则每次需要增大容量时，向量的容量将增大一倍。

(3)新增
add(E e)：将指定元素添加到此向量的末尾。

复制代码

1
2
3
4
5
6
7
public synchronized boolean add(E e) {
    modCount++;     
    ensureCapacityHelper(elementCount + 1);    //确认容器大小，如果操作容量则扩容操作
    elementData[elementCount++] = e;   //将e元素添加至末尾
    return true;
}

这个方法相对而言比较简单，具体过程就是先确认容器的大小，看是否需要进行扩容操作，然后将E元素添加到此向量的末尾。

复制代码

private void ensureCapacityHelper(int minCapacity) {
    //如果
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
	}

/**
	 * 进行扩容操作
	 * 如果此向量的当前容量小于minCapacity，则通过将其内部数组替换为一个较大的数组增加其容量。
	 * 新数据数组的大小=原来的大小 + capacityIncrement，
	 * 除非 capacityIncrement 的值小于等于零，在后一种情况下，新的容量将为原来容量的两倍，不过，如果此大小仍然小于 minCapacity，则新容量将为 minCapacity。
	 */
	private void grow(int minCapacity) {
	    int oldCapacity = elementData.length;     //当前容器大小
	    /*
	     * 新容器大小
	     * 若容量增量系数(capacityIncrement) > 0，则将容器大小增加到capacityIncrement
	     * 否则将容量增加一倍
	     */
	    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
	                                    capacityIncrement : oldCapacity);
	
	    if (newCapacity - minCapacity < 0)
	        newCapacity = minCapacity;
	
	    if (newCapacity - MAX_ARRAY_SIZE > 0)
	        newCapacity = hugeCapacity(minCapacity);
	
	    elementData = Arrays.copyOf(elementData, newCapacity);
	}

/**
	 * 判断是否超出最大范围
	 * MAX_ARRAY_SIZE：private static final int  MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	 */
	private static int hugeCapacity(int minCapacity) {
	    if (minCapacity < 0)
	        throw new OutOfMemoryError();
	    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
	}

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
private void ensureCapacityHelper(int minCapacity) {
    //如果
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
	}

	/**
	 * 进行扩容操作
	 * 如果此向量的当前容量小于minCapacity，则通过将其内部数组替换为一个较大的数组增加其容量。
	 * 新数据数组的大小=原来的大小 + capacityIncrement，
	 * 除非 capacityIncrement 的值小于等于零，在后一种情况下，新的容量将为原来容量的两倍，不过，如果此大小仍然小于 minCapacity，则新容量将为 minCapacity。
	 */
	private void grow(int minCapacity) {
	    int oldCapacity = elementData.length;     //当前容器大小
	    /*
	     * 新容器大小
	     * 若容量增量系数(capacityIncrement) > 0，则将容器大小增加到capacityIncrement
	     * 否则将容量增加一倍
	     */
	    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
	                                    capacityIncrement : oldCapacity);
	
	    if (newCapacity - minCapacity < 0)
	        newCapacity = minCapacity;
	
	    if (newCapacity - MAX_ARRAY_SIZE > 0)
	        newCapacity = hugeCapacity(minCapacity);
	
	    elementData = Arrays.copyOf(elementData, newCapacity);
	}

	/**
	 * 判断是否超出最大范围
	 * MAX_ARRAY_SIZE：private static final int  MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	 */
	private static int hugeCapacity(int minCapacity) {
	    if (minCapacity < 0)
	        throw new OutOfMemoryError();
	    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
	}

对于 Vector 整个的扩容过程，就是根据 capacityIncrement 确认扩容大小的，若 capacityIncrement <= 0 则扩大一倍，否则扩大至 capacityIncrement 。当然这个容量的最大范围为 Integer.MAX_VALUE即，2^32 – 1，所以 Vector 并不是可以无限扩充的。

（4）删除

复制代码

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
/**
* 从Vector容器中移除指定元素E
*/
public boolean remove(Object o) {
   return removeElement(o);
}

public synchronized boolean removeElement(Object obj) {
   modCount++;
   int i = indexOf(obj);   //计算obj在Vector容器中位置
   if (i >= 0) {
       removeElementAt(i);   //移除
       return true;
   }
   return false;
}

public synchronized void removeElementAt(int index) {
   modCount++;     //修改次数+1
   if (index >= elementCount) {   //删除位置大于容器有效大小
       throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
   }
   else if (index < 0) {    //位置小于 < 0
       throw new ArrayIndexOutOfBoundsException(index);
   }
   int j = elementCount - index - 1;
   if (j > 0) {   
       //从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。
       //也就是数组元素从j位置往前移
       System.arraycopy(elementData, index + 1, elementData, index, j);
   }
   elementCount--;   //容器中有效组件个数 - 1
   elementData[elementCount] = null;    //将向量的末尾位置设置为null
}

3.CopyOnWriteArraryList

(1)存储结构

复制代码

1
2
3
4
5
6
7
8
9
10
11
private volatile transient Object[] array;

//array的get和set方法
final Object[] getArray() {
    return array;
}

final void setArray(Object[] a) {
    array = a;
}

(2)构造函数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements = c.toArray();
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elements.getClass() != Object[].class)
        elements = Arrays.copyOf(elements, elements.length, Object[].class);
    setArray(elements);
}

// Creates a list holding a copy of the given array.
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

使用一个指向volatile类型的Object数组来保存容器元素。构造函数中都会根据参数值重新生成一个新的数组。

(3)新增

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 public boolean add(E e) {
    final ReentrantLock lock = this.lock;                       // 获取独占锁
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);// 重新生成一个新的数组实例，并将原始数组的元素拷贝到新数组中
        newElements[len] = e;                                   // 添加新的元素到新数组的末尾
        setArray(newElements);                                  // 更新底层数组
        return true;
    } finally {
        lock.unlock();
    }
}

第一，在”添加操作“开始前，获取独占锁(lock)，若此时有需要线程要获取锁，则必须等待；在操作完毕后，释放独占锁(lock)，此时其它线程才能获取锁。通过独占锁，来防止多线程同时修改数据！

第二，操作完毕时，会通过setArray()来更新volatile数组。对一个volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写入；这样，每次添加元素之后，其它线程都能看到新添加的元素。（volatile详情请见: java之volatile)

(4)删除

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index); // 获取volatile数组中指定索引处的元素值
        int numMoved = len - index - 1;
        if (numMoved == 0) // 如果被删除的是最后一个元素，则直接通过Arrays.copyOf()进行处理，而不需要新建数组
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);    // 拷贝删除元素前半部分数据到新数组中
            System.arraycopy(elements, index + 1, newElements, index, numMoved);// 拷贝删除元素后半部分数据到新数组中
            setArray(newElements); // 更新volatile数组
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

总结：使用volatile（可见性和防止重排）+lock（CAS）来保证并发正常进行

4.LinkedList

linkedList是一个线程不安全的双向链表
(1)定义

复制代码

1
2
3
4
public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Deque 一个线性 collection，支持在两端插入和移除元素，定义了双端队列的操作。

(2)属性

复制代码

1
2
3
private transient Entry<E> header = new Entry<E>(null, null, null);//表头
private transient int size = 0;//长度

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
private static class Entry<E> {
    E element;        //元素节点
    Entry<E> next;    //下一个元素
    Entry<E> previous;  //上一个元素

    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
}

Entry 为 LinkedList 的内部类，它定义了存储的元素。该元素的前一个元素、后一个元素，这是典型的双向链表定义方式。

(3)构造函数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
*  构造一个空列表。
*/
public LinkedList() {
    header.next = header.previous = header;
}

/**
*  构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。
*/
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

LinkedList() 构造一个空列表。里面没有任何元素，仅仅只是将 header 节点的前一个元素、后一个元素都指向自身。

LinkedList(Collection<? extends E> c)：构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。该构造函数首先会调用 LinkedList()，构造一个空列表，然后调用了 addAll() 方法将 Collection 中的所有元素添加到列表中。

(4)新增
add(E e): 将指定元素添加到此列表的结尾。

复制代码

1
2
3
4
5
public boolean add(E e) {
	addBefore(e, header);
	return true;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
private Entry<E> addBefore(E e, Entry<E> entry) {
  //利用Entry构造函数构建一个新节点 newEntry，
   Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
   //修改newEntry的前后节点的引用，确保其链表的引用关系是正确的
   newEntry.previous.next = newEntry;
   newEntry.next.previous = newEntry;
   //容量+1
   size++;
   //修改次数+1
   modCount++;
   return newEntry;
}

(5)移除

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean remove(Object o) {
    if (o==null) {
        for (Entry<E> e = header.next; e !=  header; e = e.next) {
            if (e.element==null) {
                remove(e);
                return true;
            }
        }
    } else {
        for (Entry<E> e = header.next; e != header; e = e.next) {
            if (o.equals(e.element)) {
                remove(e);
                return true;
            }
        }
    }
    return false;
}

remove(Object o)：从此列表中移除首次出现的指定元素（如果存在）。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private E remove(Entry<E> e) {
    if (e == header)
        throw new NoSuchElementException();

    //保留被移除的元素：要返回
    E result = e.element;

    //将该节点的前一节点的next指向该节点后节点
    e.previous.next = e.next;
    //将该节点的后一节点的previous指向该节点的前节点
    //这两步就可以将该节点从链表从除去：在该链表中是无法遍历到该节点的
    e.next.previous = e.previous;
    //将该节点归空
    e.next = e.previous = null;
    e.element = null;
    size--;
    modCount++;
    return result;
}

remove方法其实就是双向链表的删除节点操作。

5.Stack

(1)定义
Stack 继承 Vector，他对 Vector 进行了简单的扩展：

复制代码

1
2
public class Stack<E> extends Vector<E>

(2)方法

操作	说明
empty()	测试堆栈是否为空。
peek()	查看堆栈顶部的对象，但不从堆栈中移除它。
pop()	移除堆栈顶部的对象，并作为此函数的值返回该对象。
push(E item)	把项压入堆栈顶部。
search(Object o)	返回对象在堆栈中的位置，以 1 为基数。

(3)源码

复制代码

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
/**
 * 构造函数
 */
public Stack() {
}

/**
 *  push函数：将元素存入栈顶
 */
public E push(E item) {
    // 将元素存入栈顶。
    // addElement()的实现在Vector.java中
    addElement(item);

    return item;
}

/**
 * pop函数：返回栈顶元素，并将其从栈中删除
 */
public synchronized E pop() {
    E    obj;
    int    len = size();

    obj = peek();
    // 删除栈顶元素，removeElementAt()的实现在Vector.java中
    removeElementAt(len - 1);

    return obj;
}

/**
 * peek函数：返回栈顶元素，不执行删除操作
 */
public synchronized E peek() {
    int    len = size();

    if (len == 0)
        throw new EmptyStackException();
    // 返回栈顶元素，elementAt()具体实现在Vector.java中
    return elementAt(len - 1);
}

/**
 * 栈是否为空
 */
public boolean empty() {
    return size() == 0;
}

/**
 *  查找“元素o”在栈中的位置：由栈底向栈顶方向数
 */
public synchronized int search(Object o) {
    // 获取元素索引，elementAt()具体实现在Vector.java中
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}