Java JDK7源码-java.util.ArrayList<E>

源码

1
package java.util;
2
3
public class ArrayList<E> extends AbstractList<E>
4
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
5
{
6
    private static final long serialVersionUID = 8683452581122892189L;
7
8
    /**
9
     * 底层数组默认的初始化容量
10
     */
11
    private static final int DEFAULT_CAPACITY = 10;
12
13
    /**
14
     * 供本类空实例使用的空数组
15
     */
16
    private static final Object[] EMPTY_ELEMENTDATA = {};
17
18
    /**
19
     * 用于存储arrayList中的元素的数组
20
     * arrayList的容量即为本数组的长度
21
     * 
22
     * 使用
23
     * new ArrayList<>()声明的arrayList其内部均有:
24
     * elementData == EMPTY_ELEMENTDATA
25
     * 在插入第一个元素时elementData会被扩展为DEFAULT_CAPACITY
26
     */
27
    private transient Object[] elementData;
28
29
    /**
30
     * arrayList的长度
31
     * 注意,本字段不是arrayList的容量,而是arrayList包含的元素个数
32
     */
33
    private int size;
34
35
    /**
36
     * 以initialCapacity为初始化容量构建一个空arrayList
37
     * 
38
     * @throws IllegalArgumentException:initialCapacity < 0。
39
     */
40
    public ArrayList(int initialCapacity) {
41
        super();
42
        if (initialCapacity < 0)
43
            throw new IllegalArgumentException("Illegal Capacity: "+
44
                                               initialCapacity);
45
        this.elementData = new Object[initialCapacity];
46
    }
47
48
    /**
49
     * 以默认容量10构造一个空arrayList
50
     * 刚构造完成时数组依然是EMPTY_ELEMENTDATA,即空数组。
51
     * 需要第一个元素插入进来后才会自动扩展为长度为10的数组
52
     */
53
    public ArrayList() {
54
        super();
55
        this.elementData = EMPTY_ELEMENTDATA;
56
    }
57
58
    public ArrayList(Collection<? extends E> c) {
59
        elementData = c.toArray();
60
        size = elementData.length;
61
        // c.toArray()可能不返回Object[](见6260652)
62
        // 说明:
63
        // 因为c可以是任意的Collection实现
64
        // 而Collection对toArray()的返回值仅仅是要求Object[]
65
        // 即实际的返回可以是任意Object的子类
66
        if (elementData.getClass() != Object[].class)
67
            // 注1:Arrays.copyOf(r, i, newType)
68
            elementData = Arrays.copyOf(elementData, size, Object[].class);
69
    }
70
71
    /**
72
     * 裁剪arrayList的容量为arrayList当前的实际长度
73
     * 可以使用本方法达到arrayList的存储空间占用最小化
74
     */
75
    public void trimToSize() {
76
        // 注2:modCount
77
        modCount++;
78
        if (size < elementData.length) {
79
            // 注3:Arrays.copyOf(r, i)
80
            elementData = Arrays.copyOf(elementData, size);
81
        }
82
    }
83
84
    /**
85
     * 公开出去的API方法
86
     * 调用本方法时并不知道当前容量是否能满足minCapacity的需求
87
     * 本方法会确保当前容量能满足minCapacity的需求(即如果不够用的话则需要扩容)
88
     */
89
    public void ensureCapacity(int minCapacity) {
90
        int minExpand = (elementData != EMPTY_ELEMENTDATA)
91
            ? 0
92
            : DEFAULT_CAPACITY;
93
94
        if (minCapacity > minExpand) {
95
            ensureExplicitCapacity(minCapacity);
96
        }
97
    }
98
99
    /**
100
     * 供ArrayList类内部调用
101
     * 调用本方法时并不知道当前容量是否能满足minCapacity的需求
102
     * 本方法会确保当前容量能满足minCapacity的需求(即如果不够用的话则需要扩容)
103
     */
104
    private void ensureCapacityInternal(int minCapacity) {
105
        if (elementData == EMPTY_ELEMENTDATA) {
106
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
107
        }
108
109
        ensureExplicitCapacity(minCapacity);
110
    }
111
112
    /**
113
     * 调用本方法时并不知道当前容量是否能满足minCapacity的需求
114
     * 本方法会确保当前容量能满足minCapacity的需求(即如果不够用的话则需要扩容)
115
     */
116
    private void ensureExplicitCapacity(int minCapacity) {
117
        // 注2:modCount
118
        modCount++;
119
120
        // 内存溢出保护代码
121
        if (minCapacity - elementData.length > 0)
122
            grow(minCapacity);
123
    }
124
125
    /**
126
     * 数组能申请的最大长度
127
     * 某些JVM会在数组中存储一些头信息
128
     * 试图申请过大长度的数组可能会导致OutOfMemoryError:
129
     * 所需数组长度超过JVM限制
130
     */
131
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
132
133
    /**
134
     * 本方法被调用说明当前数组的容量确实是不够minCapacity的需求用了
135
     * 扩充数组容量以满足其至少能容纳minCapacity个元素
136
     */
137
    private void grow(int minCapacity) {
138
        int oldCapacity = elementData.length;
139
        int newCapacity = oldCapacity + (oldCapacity >> 1);
140
        if (newCapacity - minCapacity < 0)
141
            newCapacity = minCapacity;
142
        if (newCapacity - MAX_ARRAY_SIZE > 0)
143
            newCapacity = hugeCapacity(minCapacity);
144
        // 注3:Arrays.copyOf(r, i)
145
        elementData = Arrays.copyOf(elementData, newCapacity);
146
    }
147
148
    private static int hugeCapacity(int minCapacity) {
149
        if (minCapacity < 0)
150
            throw new OutOfMemoryError();
151
        return (minCapacity > MAX_ARRAY_SIZE) ?
152
            Integer.MAX_VALUE :
153
            MAX_ARRAY_SIZE;
154
    }
155
156
    /**
157
     * 重写父类:java.util.AbstractList<E>
158
     * 实现接口:java.util.List<E>
159
     * 
160
     * 返回arrayList的元素个数
161
     */
162
    public int size() {
163
        return size;
164
    }
165
166
    /**
167
     * 重写父类:java.util.AbstractList<E>
168
     * 实现接口:java.util.List<E>
169
     * 
170
     * 若arrayList不包含元素则返回true
171
     */
172
    public boolean isEmpty() {
173
        return size == 0;
174
    }
175
176
    /**
177
     * 重写父类:java.util.AbstractList<E>
178
     * 实现接口:java.util.List<E>
179
     * 
180
     * 若arrayList包含o则返回true
181
     * 更一般的来说,当且仅当arrayList至少包含一个满足如下条件的元素e时返回true:
182
     * (o==null ? e==null : o.equals(e))
183
     */
184
    public boolean contains(Object o) {
185
        return indexOf(o) >= 0;
186
    }
187
188
    /**
189
     * 重写父类:java.util.AbstractList<E>
190
     * 实现接口:java.util.List<E>
191
     * 
192
     * 返回o在arrayList中第一次出现时的索引
193
     * 若arrayList中不包含o则返回-1
194
     * 
195
     * 更一般的来说,返回满足如下条件的i的最小值:
196
     * (o==null ? get(i)==null : o.equals(get(i)))
197
     * 若无法找到满足条件的i则返回-1
198
     */
199
    public int indexOf(Object o) {
200
        if (o == null) {
201
            for (int i = 0; i < size; i++)
202
                if (elementData[i]==null)
203
                    return i;
204
        } else {
205
            for (int i = 0; i < size; i++)
206
                if (o.equals(elementData[i]))
207
                    return i;
208
        }
209
        return -1;
210
    }
211
212
    /**
213
     * 重写父类:java.util.AbstractList<E>
214
     * 实现接口:java.util.List<E>
215
     * 
216
     * 返回o在arrayList中最后一次出现时的索引
217
     * 若arrayList中不包含o则返回-1
218
     * 
219
     * 更一般的来说,返回满足如下条件的i的最大值:
220
     * (o==null ? get(i)==null : o.equals(get(i)))
221
     * 若无法找到满足条件的i则返回-1
222
     */
223
    public int lastIndexOf(Object o) {
224
        if (o == null) {
225
            for (int i = size-1; i >= 0; i--)
226
                if (elementData[i]==null)
227
                    return i;
228
        } else {
229
            for (int i = size-1; i >= 0; i--)
230
                if (o.equals(elementData[i]))
231
                    return i;
232
        }
233
        return -1;
234
    }
235
236
    /**
237
     * 重写父类:java.util.AbstractList<E>
238
     * 
239
     * 返回arrayList的一个浅拷贝(其所包含的元素本身并未被复制)
240
     */
241
    public Object clone() {
242
        try {
243
            @SuppressWarnings("unchecked")
244
            ArrayList<E> v = (ArrayList<E>) super.clone();
245
            // 注3:Arrays.copyOf(r, i)
246
            v.elementData = Arrays.copyOf(elementData, size);
247
            // # 注2:modCount
248
            v.modCount = 0;
249
            return v;
250
        } catch (CloneNotSupportedException e) {
251
            // 因ArrayList是可克隆的,因此该错误不会发生
252
            throw new InternalError();
253
        }
254
    }
255
256
    /**
257
     * 重写父类:java.util.AbstractList<E>
258
     * 实现接口:java.util.List<E>
259
     * 
260
     * 本方法是连接数组与集合的桥梁
261
     * 返回一个包含arrayList所有元素并有arrayList有相同顺序的数组
262
     * 
263
     * 返回的数组是"安全的"
264
     * 其与arrayList之间不存在引用关系(换句话说,本方法必须声明一个新的数组)
265
     * 因此调用者可以自由的修改返回的数组
266
     */
267
    public Object[] toArray() {
268
        // 注3:Arrays.copyOf(r, i)
269
        return Arrays.copyOf(elementData, size);
270
    }
271
272
    /**
273
     * 重写父类:java.util.AbstractList<E>
274
     * 实现接口:java.util.List<E>
275
     * 
276
     * 查询操作。
277
     * 本方法是连接集合与数组之间的桥梁。
278
     * 
279
     * 返回包含列表所有元素的数组。该数组的顺序与列表的固有顺序相同。返回数组的类型即为a的类型。
280
     * 具体规则的伪代码为:
281
     * if (a.length < list.size())
282
     *     不修改a,而是以a的类型新建长度为list.size()的数组并填入列表中的值,随后返回这个新生成的数组。
283
     * else if (a.length == list.size()
284
     *     将返回的结果直接填入a后返回a(若a中已有值,则a中的原值会被覆盖)。
285
     * else
286
     *     数组索引在[0, list.size() -1]的元素会被列表对应位置的元素覆盖。
287
     *     数组索引 == list.size()的元素会被置为null
288
     *     数组中后续元素(如果有的话)不变。
289
     * 
290
     * 若列表不允许包含空元素,则本方法此时可用来计算列表的长度:返回的数组第一次出现null的索引即为列表的长度。
291
     * 
292
     * 返回的数组与列表之间不存在引用关系(即使列表的底层就是基于数组实现的),数组中的元素是列表中元素的浅拷贝。
293
     * 
294
     * 小例子:
295
     * String[] y = x.toArray(new String[0]);
296
     * x是一个元素类型为String的列表,则上述语句会将x中的元素依序复制一份浅拷贝到数组y。
297
     * 
298
     * 关于本方法与前文介绍的toArray()方法,需明确:
299
     * list.toArray()
300
     * list.toArray(new Object[s])
301
     * 当s < list.size()时,上述两行代码的效果等价。
302
     * 
303
     * 本方法与前文介绍的toArray()方法很相似,可对比学习。
304
     * 
305
     * @throws ArrayStoreException a的类型列表不支持。
306
     * @throws NullPointerException null==a。
307
     */
308
    @SuppressWarnings("unchecked")
309
    public <T> T[] toArray(T[] a) {
310
        if (a.length < size)
311
            // # 注1:Arrays.copyOf(r, i, newType)
312
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
313
        // # 注4:System.arraycopy(r, 0, a, 0, i)
314
        System.arraycopy(elementData, 0, a, 0, size);
315
        if (a.length > size)
316
            a[size] = null;
317
        return a;
318
    }
319
320
321
    /**
322
     * 位置访问操作
323
     */
324
    @SuppressWarnings("unchecked")
325
    E elementData(int index) {
326
        return (E) elementData[index];
327
    }
328
329
    /**
330
     * 重写父类:java.util.AbstractList<E>
331
     * 实现接口:java.util.List<E>
332
     * 
333
     * 位置访问操作
334
     * 返回arrayList中索引位置为index的元素
335
     * 
336
     * @throws IndexOutOfBoundsException 索引越界(index < 0 || index >= size)
337
     */
338
    public E get(int index) {
339
        rangeCheck(index);
340
341
        return elementData(index);
342
    }
343
344
    /**
345
     * 重写父类:java.util.AbstractList<E>
346
     * 实现接口:java.util.List<E>
347
     * 
348
     * 以element替换arrayList中索引为index的元素。方法返回被替换的元素
349
     * 
350
     * @throws IndexOutOfBoundsException 索引越界(index < 0 || index >= size)
351
     */
352
    public E set(int index, E element) {
353
        rangeCheck(index);
354
355
        E oldValue = elementData(index);
356
        elementData[index] = element;
357
        return oldValue;
358
    }
359
360
    /**
361
     * 重写父类:java.util.AbstractList<E>
362
     * 实现接口:java.util.List<E>
363
     * 
364
     * 将e添加至arrayList末尾
365
     */
366
    public boolean add(E e) {
367
        // 该方法内部会增加modCount
368
        ensureCapacityInternal(size + 1);
369
        elementData[size++] = e;
370
        return true;
371
    }
372
373
    /**
374
     * 重写父类:java.util.AbstractList<E>
375
     * 实现接口:java.util.List<E>
376
     * 
377
     * 将element插入arrayList的index下标处
378
     * 原来处于index下标及以后的元素均向后移动一个位置
379
     * 
380
     * @throws IndexOutOfBoundsException 索引越界(index < 0 || index > size)
381
     */
382
    public void add(int index, E element) {
383
        rangeCheckForAdd(index);
384
385
        // 该方法内部会增加modCount
386
        ensureCapacityInternal(size + 1);
387
        // # 注4:System.arraycopy(r, 0, a, 0, i)
388
        System.arraycopy(elementData, index, elementData, index + 1,
389
                         size - index);
390
        elementData[index] = element;
391
        size++;
392
    }
393
394
    /**
395
     * 重写父类:java.util.AbstractList<E>
396
     * 实现接口:java.util.List<E>
397
     * 
398
     * 移除arrayList中索引值为index的元素
399
     * 后续元素左移一个位置
400
     * 返回被移除的元素
401
     * 
402
     * @throws IndexOutOfBoundsException 索引越界(index < 0 || index >= size)
403
     */
404
    public E remove(int index) {
405
        rangeCheck(index);
406
407
        // # 注2:modCount
408
        modCount++;
409
        E oldValue = elementData(index);
410
411
        int numMoved = size - index - 1;
412
        if (numMoved > 0)
413
            // # 注4:System.arraycopy(r, 0, a, 0, i)
414
            System.arraycopy(elementData, index+1, elementData, index,
415
                             numMoved);
416
        elementData[--size] = null;    // 便于GC回收
417
418
        return oldValue;
419
    }
420
421
    /**
422
     * 重写父类:java.util.AbstractList<E>
423
     * 实现接口:java.util.List<E>
424
     * 
425
     * 移除o在arrayList中第一次出现的位置的元素
426
     * 如果arrayList中不包含o则arrayList将不会被本方法改变
427
     * 
428
     * 更一般的来说,移除如下元素:
429
     * o==null ? get(i)==null : o.equals(get(i))
430
     * 其中为i满足相等条件的最小索引值
431
     * 
432
     * 若本方法改变了arrayList则返回true,反之返回false
433
     */
434
    public boolean remove(Object o) {
435
        if (o == null) {
436
            for (int index = 0; index < size; index++)
437
                if (elementData[index] == null) {
438
                    fastRemove(index);
439
                    return true;
440
                }
441
        } else {
442
            for (int index = 0; index < size; index++)
443
                if (o.equals(elementData[index])) {
444
                    fastRemove(index);
445
                    return true;
446
                }
447
        }
448
        return false;
449
    }
450
451
    private void fastRemove(int index) {
452
        // # 注2:modCount
453
        modCount++;
454
        int numMoved = size - index - 1;
455
        if (numMoved > 0)
456
            // # 注4:System.arraycopy(r, 0, a, 0, i)
457
            System.arraycopy(elementData, index+1, elementData, index,
458
                             numMoved);
459
        elementData[--size] = null;    // 便于GC回收
460
    }
461
462
    /**
463
     * 重写父类:java.util.AbstractList<E>
464
     * 实现接口:java.util.List<E>
465
     * 
466
     * 移除arrayList中的所有元素
467
     * 调用本方法后arrayList将变为空arrayList
468
     */
469
    public void clear() {
470
        // # 注2:modCount
471
        modCount++;
472
473
        // 之所以不直接将elementData置为空
474
        // 是为了保持容积不变,同时便于GC回收
475
        for (int i = 0; i < size; i++)
476
            elementData[i] = null;
477
478
        size = 0;
479
    }
480
481
    /**
482
     * 重写父类:java.util.AbstractList<E>
483
     * 实现接口:java.util.List<E>
484
     * 
485
     * 将c中所有元素插入arrayList的末尾,插入顺序为c的迭代器取出的顺序
486
     * 
487
     * 本方法并未定义如下事件发生时的解决策略:
488
     * 在将c中的元素添加至arrayList的过程中c发生变化
489
     * 这也意味着如下事件的解决策略同样未定义:
490
     * 将一个非空arrayList添加至自身
491
     * 
492
     * 若arrayList因本方法发生变化则返回true,反之返回false
493
     * 
494
     * @throws NullPointerException c==null
495
     */
496
    public boolean addAll(Collection<? extends E> c) {
497
        Object[] a = c.toArray();
498
        int numNew = a.length;
499
        ensureCapacityInternal(size + numNew);    // 增加modCount
500
        // # 注4:System.arraycopy(r, 0, a, 0, i)
501
        System.arraycopy(a, 0, elementData, size, numNew);
502
        size += numNew;
503
        return numNew != 0;
504
    }
505
506
    /**
507
     * 重写父类:java.util.AbstractList<E>
508
     * 实现接口:java.util.List<E>
509
     * 
510
     * 将c中所有元素插入arrayList的指定位置(index)
511
     * 插入顺序为c的迭代器取出的顺序
512
     * 原index位置及以后位置的元素顺次向后移动,空出装载c的位置
513
     * 
514
     * 若arrayList因本方法发生变化则返回true,反之返回false
515
     * 
516
     * @throws IndexOutOfBoundsException 索引越界(index < 0 || index > size)
517
     * @throws NullPointerException c==null
518
     */
519
    public boolean addAll(int index, Collection<? extends E> c) {
520
        rangeCheckForAdd(index);
521
522
        Object[] a = c.toArray();
523
        int numNew = a.length;
524
        ensureCapacityInternal(size + numNew);    // 增加modCount
525
526
        int numMoved = size - index;
527
        if (numMoved > 0)
528
            // # 注4:System.arraycopy(r, 0, a, 0, i)
529
            System.arraycopy(elementData, index, elementData, index + numNew,
530
                             numMoved);
531
532
        System.arraycopy(a, 0, elementData, index, numNew);
533
        size += numNew;
534
        return numNew != 0;
535
    }
536
537
    /**
538
     * 重写父类:java.util.AbstractList<E>
539
     * 
540
     * 从arrayList中移除索引为[fromIndex,toIndex)的元素
541
     * 并将后续元素左移
542
     * 本方法减少了arrayList (toIndex - fromIndex)个元素
543
     * 若toIndex==fromIndex,本方法不产生实际效果
544
     * 
545
     * @throws IndexOutOfBoundsException 索引越界(fromIndex < 0 || fromIndex >= size() || toIndex > size() || toIndex < fromIndex)
546
     */
547
    protected void removeRange(int fromIndex, int toIndex) {
548
        modCount++;
549
        int numMoved = size - toIndex;
550
        // # 注4:System.arraycopy(r, 0, a, 0, i)
551
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
552
                         numMoved);
553
554
        int newSize = size - (toIndex-fromIndex);
555
        // 便于GC回收
556
        for (int i = newSize; i < size; i++) {
557
            elementData[i] = null;
558
        }
559
        size = newSize;
560
    }
561
562
    /**
563
     * 检查index是否在边界之内
564
     * 若不在,则抛出一个适当的运行时异常
565
     * 
566
     * 本方法不会检查index<0的情况:
567
     * 因为访问数组时索引>=0是前提条件
568
     * 若index<0,则数组会自行抛出ArrayIndexOutOfBoundsException
569
     */
570
    private void rangeCheck(int index) {
571
        if (index >= size)
572
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
573
    }
574
575
    /**
576
     * add及addAll方法所使用的边界检查方法
577
     */
578
    private void rangeCheckForAdd(int index) {
579
        if (index > size || index < 0)
580
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
581
    }
582
583
    /**
584
     * 构建一个IndexOutOfBoundsException的详细信息
585
     * 在众多可能的错误处理代码中
586
     * 这种"溢出"的处理代码在server及client JVM中均有最佳的性能
587
     */
588
    private String outOfBoundsMsg(int index) {
589
        return "Index: "+index+", Size: "+size;
590
    }
591
592
    /**
593
     * 重写父类:java.util.AbstractList<E>
594
     * 实现接口:java.util.List<E>
595
     * 
596
     * 从arrayList中移除所有与c的交集元素(求差集)
597
     * 若arrayList因本方法发生变化则返回true,反之返回false
598
     * 
599
     * @throws ClassCastException arrayList中至少有一个元素的类型与c不相容
600
     * @throws NullPointerException arrayList中至少有一个元素为null且c不允许null存在;或c==null
601
     */
602
    public boolean removeAll(Collection<?> c) {
603
        // # 注5:batchRemove(c, b)
604
        return batchRemove(c, false);
605
    }
606
607
    /**
608
     * 重写父类:java.util.AbstractList<E>
609
     * 实现接口:java.util.List<E>
610
     * 
611
     * 保留arrayList与c的交集元素
612
     * 若arrayList因本方法发生变化则返回true,反之返回false
613
     * 
614
     * @throws ClassCastException arrayList中至少有一个元素的类型与c不相容
615
     * @throws NullPointerException arrayList中至少有一个元素为null且c不允许null存在;或c==null
616
     */
617
    public boolean retainAll(Collection<?> c) {
618
        // # 注5:batchRemove(c, b)
619
        return batchRemove(c, true);
620
    }
621
622
    private boolean batchRemove(Collection<?> c, boolean complement) {
623
        final Object[] elementData = this.elementData;
624
        int r = 0, w = 0;
625
        boolean modified = false;
626
        try {
627
            for (; r < size; r++)
628
                if (c.contains(elementData[r]) == complement)    // complement == true:移除arrayList中与c不同的元素,retainAll调用。
629
                                                                 // complement == false:移除arrayList中与c相同的元素,removeAll调用。
630
                    elementData[w++] = elementData[r];
631
        } finally {
632
            // 在c.contains()抛出异常时兼容AbstractCollection的保护性行为
633
            if (r != size) {    // 进入此if说明try中的for循环未完成,即c.contains()在循环过程中抛出了异常
634
                                // 此时从抛出异常的索引值r起的后续元素均不应再参与remove行为了,即索引在[r,size-1]之间的元素原样保留。
635
                // # 注4:System.arraycopy(r, 0, a, 0, i)
636
                System.arraycopy(elementData, r,
637
                                 elementData, w,
638
                                 size - r);
639
                w += size - r;
640
            }
641
            if (w != size) {    // 进入此if说明确实成功移除了元素。
642
                                // 则应标明已移除并修改size等属性。
643
                for (int i = w; i < size; i++)
644
                    elementData[i] = null;
645
                modCount += size - w;
646
                size = w;
647
                modified = true;
648
            }
649
        }
650
        return modified;
651
    }
652
653
    /**
654
     * 将arrayList的状态保存至流中(序列化时使用)
655
     * 
656
     * 流中存储的信息为:
657
     * 1. arrayList本身的信息。
658
     * 2. arrayList的长度。
659
     * 3. arrayList中的元素按序排列。
660
     * 
661
     * @throws java.io.IOException
662
     */
663
    private void writeObject(java.io.ObjectOutputStream s)
664
        throws java.io.IOException{
665
        // # 注2:modCount
666
        int expectedModCount = modCount;
667
        s.defaultWriteObject();    // arrayList本身的信息
668
669
        s.writeInt(size);    // 长度
670
671
        for (int i=0; i<size; i++) {    // arrayList中的元素
672
            s.writeObject(elementData[i]);
673
        }
674
675
        if (modCount != expectedModCount) {
676
            throw new ConcurrentModificationException();
677
        }
678
    }
679
680
    /**
681
     * 反序列化时从流中恢复arrayList
682
     * 
683
     * @throws java.io.IOException
684
     * @throws ClassNotFoundException
685
     */
686
    private void readObject(java.io.ObjectInputStream s)
687
        throws java.io.IOException, ClassNotFoundException {
688
        elementData = EMPTY_ELEMENTDATA;
689
690
        s.defaultReadObject();    // arrayList本身的信息
691
692
        s.readInt();    // 长度
693
694
        if (size > 0) {
695
            // 类似于clone(),声明所需大小的数组
696
            ensureCapacityInternal(size);
697
698
            Object[] a = elementData;
699
            for (int i=0; i<size; i++) {    // 依次读入流中所有元素
700
                a[i] = s.readObject();
701
            }
702
        }
703
    }
704
705
    /**
706
     * 重写父类:java.util.AbstractList<E>
707
     * 实现接口:java.util.List<E>
708
     * 
709
     * 返回一个arrayList按固有顺序迭代的listIterator
710
     * 迭代开始时游标位于索引[index-1,index]之间
711
     * 
712
     * 即使用本方法得到listIterator后
713
     * 若第一次调用的是listIterator.next(),返回的元素的索引是index;
714
     * 同理,若第一次调用的是listIterator.previous(),返回的是索引为index-1的元素
715
     * 
716
     * 返回的listIterator遵循fail-fast原则
717
     * 
718
     * @throws IndexOutOfBoundsException 索引越界(index < 0 || index > size)
719
     */
720
    public ListIterator<E> listIterator(int index) {
721
        if (index < 0 || index > size)
722
            throw new IndexOutOfBoundsException("Index: "+index);
723
        return new ListItr(index);
724
    }
725
726
    /**
727
     * 重写父类:java.util.AbstractList<E>
728
     * 实现接口:java.util.List<E>
729
     * 
730
     * 返回一个arrayList按固有顺序迭代的listIterator
731
     * 返回的listIterator遵循fail-fast原则
732
     */
733
    public ListIterator<E> listIterator() {
734
        return new ListItr(0);
735
    }
736
737
    /**
738
     * 重写父类:java.util.AbstractList<E>
739
     * 实现接口:java.util.List<E>
740
     * 
741
     * 返回一个arrayList按固有顺序迭代的iterator
742
     * 返回的iterator遵循fail-fast原则
743
     */
744
    public Iterator<E> iterator() {
745
        return new Itr();
746
    }
747
748
    /**
749
     * Iterator在ArrayList的最优实现
750
     */
751
    private class Itr implements Iterator<E> {
752
753
        /**
754
         * 游标位于元素[cursor-1,cursor]之间
755
         */
756
        int cursor;
757
758
        /**
759
         * 上一次操作的元素的索引
760
         * 即调用next()或previous()后赋以对应的值
761
         * 初始时或调用remove()或add(E e)后置为-1
762
         */
763
        int lastRet = -1;
764
765
        /**
766
         * iterator认为的arrayList发生的结构性变化的次数
767
         * 初始时同步自其所属的arrayList
768
         */
769
        int expectedModCount = modCount;
770
771
        /**
772
         * 实现接口:java.util.Iterator<E>
773
         */
774
        public boolean hasNext() {
775
            return cursor != size;
776
        }
777
778
        /**
779
         * 实现接口:java.util.Iterator<E>
780
         */
781
        @SuppressWarnings("unchecked")
782
        public E next() {
783
            checkForComodification();
784
            int i = cursor;
785
            if (i >= size)
786
                throw new NoSuchElementException();
787
            Object[] elementData = ArrayList.this.elementData;
788
            if (i >= elementData.length)
789
                throw new ConcurrentModificationException();
790
            cursor = i + 1;
791
            return (E) elementData[lastRet = i];
792
        }
793
794
        /**
795
         * 实现接口:java.util.Iterator<E>
796
         */
797
        public void remove() {
798
            if (lastRet < 0)
799
                throw new IllegalStateException();
800
            checkForComodification();
801
802
            try {
803
                ArrayList.this.remove(lastRet);
804
                cursor = lastRet;
805
                lastRet = -1;
806
                expectedModCount = modCount;
807
            } catch (IndexOutOfBoundsException ex) {
808
                throw new ConcurrentModificationException();
809
            }
810
        }
811
812
        final void checkForComodification() {
813
            if (modCount != expectedModCount)
814
                throw new ConcurrentModificationException();
815
        }
816
    }
817
818
    /**
819
     * ListIterator在arrayList的最优实现
820
     */
821
    private class ListItr extends Itr implements ListIterator<E> {
822
        ListItr(int index) {
823
            super();
824
            cursor = index;
825
        }
826
827
        /**
828
         * 实现接口:java.util.ListIterator<E>
829
         */
830
        public boolean hasPrevious() {
831
            return cursor != 0;
832
        }
833
834
        /**
835
         * 实现接口:java.util.ListIterator<E>
836
         */
837
        public int nextIndex() {
838
            return cursor;
839
        }
840
841
        /**
842
         * 实现接口:java.util.ListIterator<E>
843
         */
844
        public int previousIndex() {
845
            return cursor - 1;
846
        }
847
848
        /**
849
         * 实现接口:java.util.ListIterator<E>
850
         */
851
        @SuppressWarnings("unchecked")
852
        public E previous() {
853
            checkForComodification();
854
            int i = cursor - 1;
855
            if (i < 0)
856
                throw new NoSuchElementException();
857
            Object[] elementData = ArrayList.this.elementData;
858
            if (i >= elementData.length)
859
                throw new ConcurrentModificationException();
860
            cursor = i;
861
            return (E) elementData[lastRet = i];
862
        }
863
864
        /**
865
         * 实现接口:java.util.ListIterator<E>
866
         */
867
        public void set(E e) {
868
            if (lastRet < 0)
869
                throw new IllegalStateException();
870
            checkForComodification();
871
872
            try {
873
                ArrayList.this.set(lastRet, e);
874
            } catch (IndexOutOfBoundsException ex) {
875
                throw new ConcurrentModificationException();
876
            }
877
        }
878
879
        /**
880
         * 实现接口:java.util.ListIterator<E>
881
         */
882
        public void add(E e) {
883
            checkForComodification();
884
885
            try {
886
                int i = cursor;
887
                ArrayList.this.add(i, e);
888
                cursor = i + 1;
889
                lastRet = -1;
890
                expectedModCount = modCount;
891
            } catch (IndexOutOfBoundsException ex) {
892
                throw new ConcurrentModificationException();
893
            }
894
        }
895
    }
896
897
    /**
898
     * 重写父类:java.util.AbstractList<E>
899
     * 实现接口:java.util.List<E>
900
     * 
901
     * 返回arrayList的一部分,索引值区间:
902
     * [fromIndex,toIndex)
903
     * 特别的,若fromIndex==toIndex,则返回空arrayList(不是null)
904
     * 
905
     * 返回的arrayList是原arrayList的一个视图
906
     * 前者是后者的一部分,并未从后者中分离出去
907
     * 因此作用在前者之上的修改会反映在后者上,反之亦然
908
     * 
909
     * 使用本方法的好处在于
910
     * 当我们操作arrayList的一部分时
911
     * 可以直接在这一部分内部操作(仿佛这就是一个新的arrayList)
912
     * 而无需被各种索引的边界分散过多的注意
913
     * 
914
     * 例如,如果想批量移除arrayList中的一部分,可按如下操作:
915
     * arrayList.subList(from, to).clear();
916
     * 
917
     * 同理,所有本类的方法及所有
918
     * java.util.Collections类
919
     * 提供的静态方法均支持subList取得的视图作为一个独立的arrayList调用
920
     * 例如:
921
     * arrayList2 = arrayList.subList(1, 2);
922
     * arrayList2.get(0);
923
     * 此时取得的元素即为arrayList.get(1)
924
     * 
925
     * 若在生成视图后原arrayList发生了结构性的变化(例如长度发生了变化)
926
     * 则已生成的视图将被重置为未定义的状态
927
     * 
928
     * @throws IndexOutOfBoundsException 索引越界(fromIndex < 0 || toIndex > size)
929
     * @throws IllegalArgumentException fromIndex > toIndex
930
     */
931
    public List<E> subList(int fromIndex, int toIndex) {
932
        subListRangeCheck(fromIndex, toIndex, size);
933
        return new SubList(this, 0, fromIndex, toIndex);
934
    }
935
936
    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
937
        if (fromIndex < 0)
938
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
939
        if (toIndex > size)
940
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
941
        if (fromIndex > toIndex)
942
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
943
                                               ") > toIndex(" + toIndex + ")");
944
    }
945
946
    private class SubList extends AbstractList<E> implements RandomAccess {
947
        /**
948
         * 本视图的父亲list
949
         * 注意:
950
         * parent代表的是近亲父亲,也就是说依然可能是个视图,而非始祖
951
         * 
952
         * 例如始祖list生成了视图sublist1
953
         * sublist1生成了视图sublist2
954
         * sublist1的parent为list
955
         * sublist2的parent为sublist1
956
         */
957
        private final AbstractList<E> parent;
958
959
        /**
960
         * 本视图相对于父亲list的位移量
961
         * 
962
         * 例如有始祖list
963
         * list使用subList(f, t)得到了subList1
964
         * 则subList1的parent为list,parentOffset=f
965
         */
966
        private final int parentOffset;
967
968
        /**
969
         * 本视图相对于始祖的位移量
970
         */
971
        private final int offset;
972
973
        /**
974
         * 本视图长度
975
         */
976
        int size;
977
978
        /**
979
         * @param parent AbstractList<E>, 父亲list
980
         * @param offset int, 父亲list相对于始祖的位移
981
         * @param fromIndex int, 本视图相对于父亲list的位移
982
         * @param toIndex int, 本视图相对于父亲list的位移结束量。实际本视图包含的元素为父亲list中的[fromIndex,toIndex)
983
         */
984
        SubList(AbstractList<E> parent,
985
                int offset, int fromIndex, int toIndex) {
986
            this.parent = parent;
987
            this.parentOffset = fromIndex;
988
            this.offset = offset + fromIndex;
989
            this.size = toIndex - fromIndex;
990
            this.modCount = ArrayList.this.modCount;
991
        }
992
993
        /**
994
         * 重写父类:java.util.AbstractList<E>
995
         */
996
        public E set(int index, E e) {
997
            rangeCheck(index);
998
            checkForComodification();
999
            E oldValue = ArrayList.this.elementData(offset + index);
1000
            ArrayList.this.elementData[offset + index] = e;
1001
            return oldValue;
1002
        }
1003
1004
        /**
1005
         * 重写父类:java.util.AbstractList<E>
1006
         */
1007
        public E get(int index) {
1008
            rangeCheck(index);
1009
            checkForComodification();
1010
            return ArrayList.this.elementData(offset + index);
1011
        }
1012
1013
        public int size() {
1014
            checkForComodification();
1015
            return this.size;
1016
        }
1017
1018
        /**
1019
         * 重写父类:java.util.AbstractList<E>
1020
         * 
1021
         * 本方法之所以使用了parent的add方法而非始祖的add方法
1022
         * 是因为本方法使始祖list发生了结构性变化
1023
         * 这种变化必须通知到本视图的所有前辈
1024
         */
1025
        public void add(int index, E e) {
1026
            rangeCheckForAdd(index);
1027
            checkForComodification();
1028
            parent.add(parentOffset + index, e);
1029
            this.modCount = parent.modCount;
1030
            this.size++;
1031
        }
1032
1033
        /**
1034
         * 重写父类:java.util.AbstractList<E>
1035
         * 
1036
         * 本方法之所以使用了parent的remove方法而非始祖的remove方法
1037
         * 是因为本方法使始祖list发生了结构性变化
1038
         * 这种变化必须通知到本视图的所有前辈
1039
         */
1040
        public E remove(int index) {
1041
            rangeCheck(index);
1042
            checkForComodification();
1043
            E result = parent.remove(parentOffset + index);
1044
            this.modCount = parent.modCount;
1045
            this.size--;
1046
            return result;
1047
        }
1048
1049
        /**
1050
         * 重写父类:java.util.AbstractList<E>
1051
         * 
1052
         * 本方法之所以使用了parent的removeRange方法而非始祖的removeRange方法
1053
         * 是因为本方法使始祖list发生了结构性变化
1054
         * 这种变化必须通知到本视图的所有前辈
1055
         */
1056
        protected void removeRange(int fromIndex, int toIndex) {
1057
            checkForComodification();
1058
            parent.removeRange(parentOffset + fromIndex,
1059
                               parentOffset + toIndex);
1060
            this.modCount = parent.modCount;
1061
            this.size -= toIndex - fromIndex;
1062
        }
1063
1064
        /**
1065
         * 重写父类:java.util.AbstractList<E>
1066
         */
1067
        public boolean addAll(Collection<? extends E> c) {
1068
            return addAll(this.size, c);
1069
        }
1070
1071
        /**
1072
         * 重写父类:java.util.AbstractList<E>
1073
         * 
1074
         * 本方法之所以使用了parent的addAll方法而非始祖的addAll方法
1075
         * 是因为本方法使始祖list发生了结构性变化
1076
         * 这种变化必须通知到本视图的所有前辈
1077
         */
1078
        public boolean addAll(int index, Collection<? extends E> c) {
1079
            rangeCheckForAdd(index);
1080
            int cSize = c.size();
1081
            if (cSize==0)
1082
                return false;
1083
1084
            checkForComodification();
1085
            parent.addAll(parentOffset + index, c);
1086
            this.modCount = parent.modCount;
1087
            this.size += cSize;
1088
            return true;
1089
        }
1090
1091
        /**
1092
         * 重写父类:java.util.AbstractList<E>
1093
         */
1094
        public Iterator<E> iterator() {
1095
            // 本类并未重写listIterator()方法
1096
            // 因此这里调用的是父类AbstractList的listIterator()方法
1097
            // 父类AbstractList的listIterator()方法实际调用的是listIterator(0)
1098
            // 而本类重写了listIterator(i)
1099
            // 故最终实际调用的是本类的listIterator(i)
1100
            return listIterator();
1101
        }
1102
1103
        /**
1104
         * 重写父类:java.util.AbstractList<E>
1105
         * 
1106
         * 入参index是相对本视图内部的索引值
1107
         */
1108
        public ListIterator<E> listIterator(final int index) {
1109
            checkForComodification();
1110
            rangeCheckForAdd(index);
1111
            final int offset = this.offset;
1112
1113
            return new ListIterator<E>() {
1114
                int cursor = index;
1115
                int lastRet = -1;
1116
                int expectedModCount = ArrayList.this.modCount;
1117
1118
                public boolean hasNext() {
1119
                    return cursor != SubList.this.size;
1120
                }
1121
1122
                @SuppressWarnings("unchecked")
1123
                public E next() {
1124
                    checkForComodification();
1125
                    int i = cursor;
1126
                    if (i >= SubList.this.size)
1127
                        throw new NoSuchElementException();
1128
                    Object[] elementData = ArrayList.this.elementData;
1129
                    if (offset + i >= elementData.length)
1130
                        throw new ConcurrentModificationException();
1131
                    cursor = i + 1;
1132
                    return (E) elementData[offset + (lastRet = i)];
1133
                }
1134
1135
                public boolean hasPrevious() {
1136
                    return cursor != 0;
1137
                }
1138
1139
                @SuppressWarnings("unchecked")
1140
                public E previous() {
1141
                    checkForComodification();
1142
                    int i = cursor - 1;
1143
                    if (i < 0)
1144
                        throw new NoSuchElementException();
1145
                    Object[] elementData = ArrayList.this.elementData;
1146
                    if (offset + i >= elementData.length)
1147
                        throw new ConcurrentModificationException();
1148
                    cursor = i;
1149
                    return (E) elementData[offset + (lastRet = i)];
1150
                }
1151
1152
                public int nextIndex() {
1153
                    return cursor;
1154
                }
1155
1156
                public int previousIndex() {
1157
                    return cursor - 1;
1158
                }
1159
1160
                public void remove() {
1161
                    if (lastRet < 0)
1162
                        throw new IllegalStateException();
1163
                    checkForComodification();
1164
1165
                    try {
1166
                        SubList.this.remove(lastRet);
1167
                        cursor = lastRet;
1168
                        lastRet = -1;
1169
                        expectedModCount = ArrayList.this.modCount;
1170
                    } catch (IndexOutOfBoundsException ex) {
1171
                        throw new ConcurrentModificationException();
1172
                    }
1173
                }
1174
1175
                public void set(E e) {
1176
                    if (lastRet < 0)
1177
                        throw new IllegalStateException();
1178
                    checkForComodification();
1179
1180
                    try {
1181
                        ArrayList.this.set(offset + lastRet, e);
1182
                    } catch (IndexOutOfBoundsException ex) {
1183
                        throw new ConcurrentModificationException();
1184
                    }
1185
                }
1186
1187
                public void add(E e) {
1188
                    checkForComodification();
1189
1190
                    try {
1191
                        int i = cursor;
1192
                        SubList.this.add(i, e);
1193
                        cursor = i + 1;
1194
                        lastRet = -1;
1195
                        expectedModCount = ArrayList.this.modCount;
1196
                    } catch (IndexOutOfBoundsException ex) {
1197
                        throw new ConcurrentModificationException();
1198
                    }
1199
                }
1200
1201
                final void checkForComodification() {
1202
                    if (expectedModCount != ArrayList.this.modCount)
1203
                        throw new ConcurrentModificationException();
1204
                }
1205
            };
1206
        }
1207
1208
        /**
1209
         * 重写父类:java.util.AbstractList<E>
1210
         */
1211
        public List<E> subList(int fromIndex, int toIndex) {
1212
            subListRangeCheck(fromIndex, toIndex, size);
1213
            return new SubList(this, offset, fromIndex, toIndex);
1214
        }
1215
1216
        private void rangeCheck(int index) {
1217
            if (index < 0 || index >= this.size)
1218
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1219
        }
1220
1221
        private void rangeCheckForAdd(int index) {
1222
            if (index < 0 || index > this.size)
1223
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1224
        }
1225
1226
        private String outOfBoundsMsg(int index) {
1227
            return "Index: "+index+", Size: "+this.size;
1228
        }
1229
1230
        private void checkForComodification() {
1231
            if (ArrayList.this.modCount != this.modCount)
1232
                throw new ConcurrentModificationException();
1233
        }
1234
    }
1235
}

已整理层级关系

本类直接继承的类

本类直接实现的接口

综述

本类是Java集合框架中的一员,底层基于数组实现了List接口。

本类实现了List接口所有可选的操作,允许包含null在内的所有元素。除了实现List接口外,本类还提供调整本类内部用于存储arrayList的数组的长度的方法。

除了Vector不具备序列化能力及本类不具备线程安全的能力外,粗略的讲,可以认为本类与Vector等价。

size(),isEmpty(),get(int index),set(int index, E element),iterator(),listIterator()时间复杂度为O(1)。add(E e)的时间复杂度为常数恒定分摊时间(添加一个元素为O(1),若需扩容则需大于O(1)的时间),即:添加n个元素需要O(n)的时间。所有其他的操作花费线性阶的时间(粗略的讲)。总体来说,时间复杂度较之LinkedList要低。


capacity

每一个本类的实例都有一个容量,容量是指被用于存储arrayList中的元素的数组的长度。它的长度总是至少等于arrayList的长度。随着元素被插入arrayList,该数组的长度会自动增长。只要满足添加一个元素的时间复杂度为常数恒定分摊时间即可,对于扩容策略的细节并未有强制规定。

使用时,可以在向list中添加大量元素前使用ensureCapacity(int minCapacity)对arrayList进行扩容。这样可以减少重新分配增量空间的次数。

synchronized

注意,本实现是线程不安全的。如果复数个线程同时访问一个arrayList实例,并且至少一个线程对arrayList做出了结构性修改(结构性操作是指任何添加或删除一个或一个以上元素的操作,或者更确切的说,改变了内部数组的大小。仅仅只是设置一个元素的值不是结构性变化),则必须要在调用外部保证线程安全。通常来说,这种线程安全性需要容器本身来确保(例如Vector),不过,如果实在是需要在并发环境下使用线程不安全的list,例如本类,则可用

1
Collections.synchronizedList(List<T> list)

封装。即:

1
List list = Collections.synchronizedList(new ArrayList(...));

该操作最好在声明arrayList时即进行,以避免意外情况下会有线程不安全的访问请求arrayList。

fail-fast

本类iterator()及listIterator()返回的迭代器采用快速失败模式:在迭代器创建后,若arrayList在任何时候以任何方式发生了结构性变化,除非原因是因为迭代器本身触发(具体来说:ListIterator.remove()及ListIterator.add(E e)),否则迭代器会抛出ConcurrentModificationException。因此,在面对并发性修改时,迭代器会简单明了的失败,而非依据实际的改变情况,在未来采取不确定的行为。

事实上,fail-fast模式并不能完全根除线程不安全的并发修改。它只是尽力而为:若实在力有不逮则迭代器会抛出ConcurrentModificationException。因此在程序中完全依靠fail-fast避免线程安全问题是错误的:fail-fast模式应该只被用于检测bug。

注1:Arrays.copyOf(r, i, newType)

1
Arrays.copyOf(U[] r, int i, Class<? extends T[]> newType)

以r为基础返回一个长度为i的数组,返回数组的类型为newType。

  • 若i<r.length则r发生截断。实际返回的数组为r中索引为[0,i-1]的元素。
  • 若i==r.length,则返回的数组与r相等。
  • 若i>r.length,返回的数组中索引为[0, r.length-1]的元素为r中对应位置的元素,索引为[r.length, i-1]的元素以null填充。

无论如何,返回的数组都是新生成的,与r不存在引用关系。返回的数组中的元素是r中元素的浅拷贝。

注2:modCount

modCount字段继承自超类AbstractList:

list发生结构性变化的次数。结构性变化是指改变list的长度,或是其他会使迭代器结果混乱的变化。

本字段将被iterator()返回的iterator及listIterator()返回的listIterator使用。若本字段发生了 iterator/listIterator 所没有预期到的变化,则在调用 iterator/listIterator 的next(),remove(),previous(),set(E e),add(E e)出现fail-fast时抛出ConcurrentModificationException。

在迭代过程中,若检测到并发性变化,则直接判定为失败并抛出异常(fail-fast),而不会去进一步检测所发生的并发性变化是否真的会对迭代造成影响(non-deterministic)。

子类可自行选择是否使用本字段。若子类决定继承本类的fail-fast判定,则只需要在会引发结构性变化的方法中增加本字段的值。本类中已实现的引发结构性变化的方法有add(int index, E element)及remove(int index)。调用一次add(int index, E element)或remove(int index)只需将本字段自增1,表示发生了一次结构性变化,否则 iterator/listIterator 会抛出错误的ConcurrentModificationException。

若子类不想遵循fail-fast,忽略本字段即可。

注3:Arrays.copyOf(r, i)

以r为基础返回一个长度为i的数组。

  • 若i<r.length则r发生截断。实际返回的数组为r中索引为[0,i-1]的元素。
  • 若i==r.length,则返回的数组与r相等。
  • 若i>r.length,返回的数组中索引为[0, r.length-1]的元素为r中对应位置的元素,索引为[r.length, i-1]的元素以null填充。

无论如何,返回的数组都是新生成的,与r不存在引用关系。返回的数组中的元素是r中元素的浅拷贝。

注4:System.arraycopy(r, 0, a, 0, i)

参数含义依次为:

  1. r: 待复制的源数组。
  2. 0: 源数组中开始复制的索引。
  3. a: 复制目标数组。
  4. 0: 目标数组中接收元素的起始索引。
  5. i: 复制的元素个数。

目标数组中其他位置的元素不受影响。

注5:batchRemove(c, b)

第二个参数的类型为boolean,其含义为:

  • true:移除arrayList中与c不同的元素。
  • false:移除arrayList中与c相同的元素。