释放双眼，带上耳机，听听看~！
1.List接口
该接口继承了Collection接口的方法，除此还有一些特殊的扩展接口。
-
List是Collection体系中，一个子接口分支，该接口允许插入重复元素，支持通过索引，随机的访问集合中的元素。
-
列表通常允许重复的元素。 更正式地，列表通常允许元素e1和e2成对使得e1.equals(e2) ，并且如果它们允许空元素，它们通常允许多个空元素。
-
List接口提供了两种方法来搜索指定的对象。 从性能角度来说，谨慎使用这些方法。 在许多实现中，它们将执行昂贵的线性搜索。
-
List接口提供了一个特殊的迭代器，称为ListIterator，其允许元件插入和更换，并且除了该Iterator接口提供正常操作的双向访问。 提供了一种方法来获取从列表中的指定位置开始的列表迭代器。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2 //返回此列表中指定位置的元素。
3 E get(int index);
4 //替换指定位置的元素,index索引是[0,size());
5 E set(int index, E element);
6 //将指定的元素插入此列表中的指定位置（可选操作）。 将当前位于该位置的元素（如果有）和任何后续元素（向其索引添加一个）移动。索引是[0,size()],当index=size()时，就是在尾部插入
7 void add(int index, E element);
8 //指定元素的下标，没有返回-1
9 int indexOf(Object o);
10 //返回列表中的列表迭代器（按适当的顺序）。
11 ListIterator<E> listIterator();
12 //从列表中的指定位置开始，返回列表中的元素（按正确顺序）的列表迭代器。 指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。
13 ListIterator<E> listIterator(int index)
14}
15
16
2.ListIterator<E>接口
接口是Iterator<E>的子接口，该接口除了定义实现了接口的类除了有后续迭代和移除的功能外，还支持向前遍历.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2 boolean hasNext();
3
4 E next();
5 //是针对于当前元素位置进行判断
6 boolean hasPrevious();
7 //返回由后续调用返回的元素的索引next() 。 （如果列表迭代器位于列表的末尾，则返回列表大小。）
8 E previous();
9 //返回由后续调用previous()返回的元素的索引。 （如果列表迭代器位于列表的开头，则返回-1）
10 int previousIndex();
11 //用指定的元素（可选操作）替换由next()返回的最后一个元素或previous() 。
12 void set(E e);
13}
14
15
3.AbstractList<E>的实现
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
2 //逆序查找指定元素，支持o为null
3 public int lastIndexOf(Object o) {
4 //返回一个指定遍历到指定位置ListIterator对象，然后向前遍历
5 ListIterator<E> it = listIterator(size());
6 if (o==null) {
7 while (it.hasPrevious())
8 if (it.previous()==null)
9 return it.nextIndex();
10 } else {
11 while (it.hasPrevious())
12 if (o.equals(it.previous()))
13 return it.nextIndex();
14 }
15 return -1;
16 }
17 //返回一个元素迭代器
18 //此实现返回一个简单的实现Iterator接口，依托后台列表的size(),get(int)和remove(int)方法。
19 //（protected） modCount字段的规范中所描述的那样，这种实现可以面对并发修改来抛出运行时异常。
20 public Iterator<E> iterator() {
21 return new Itr();
22 }
23
24 //迭代器的简单实现
25 private class Itr implements Iterator<E> {
26 /**
27 * Index of element to be returned by subsequent call to next.
28 *集合中的元素下一次要返回的元素下表
29 */
30 int cursor = 0;
31
32 /**
33 * Index of element returned by most recent call to next or
34 * previous. Reset to -1 if this element is deleted by a call
35 * to remove.
36 * 返回下标，下表是最近一次的next()返回元素的下标。
37 */
38 int lastRet = -1;
39
40 //集合中的元素删除,则会改变modCount的数值
41 int expectedModCount = modCount;
42
43 //当游标不等于集合大小时，则还可以元素尚未迭代完毕
44 public boolean hasNext() {
45 return cursor != size();
46 }
47
48 //返回当前游标对应的元素，返回后，将游标下移
49 public E next() {
50 //检查是否其他线程并发修改了元素
51 checkForComodification();
52 try {
53 int i = cursor;
54 E next = get(i);
55 lastRet = i;//记录最新的返回元素索引
56 cursor = i + 1;//游标++
57 return next;
58 } catch (IndexOutOfBoundsException e) {
59 checkForComodification();
60 throw new NoSuchElementException();
61 }
62 }
63
64 //移除元素，
65 public void remove() {
66 if (lastRet < 0)
67 throw new IllegalStateException();
68 checkForComodification();//fast-fail 检查
69
70 try {
71 AbstractList.this.remove(lastRet);//移除上次操作元素
72 if (lastRet < cursor)
73 cursor--;//游标上移，移除元素后，当前位置，应该是要迭代的下一个元素
74 lastRet = -1;
75 expectedModCount = modCount;
76 } catch (IndexOutOfBoundsException e) {
77 throw new ConcurrentModificationException();
78 }
79 }
80
81 final void checkForComodification() {
82 if (modCount != expectedModCount)
83 throw new ConcurrentModificationException();
84 }
85 }
86
87 //返回一个可以任意方向遍历的迭代器对象
88 public ListIterator<E> listIterator() {
89 return listIterator(0);
90 }
91
92 private class ListItr extends Itr implements ListIterator<E> {
93 //传入当前迭代的位置
94 ListItr(int index) {
95 cursor = index;
96 }
97
98 public boolean hasPrevious() {
99 return cursor != 0;
100 }
101
102 //前一个元素，当前元素的前一个元素
103 public E previous() {
104 checkForComodification();
105 try {
106 int i = cursor - 1;
107 E previous = get(i);
108 lastRet = cursor = i;
109 return previous;
110 } catch (IndexOutOfBoundsException e) {
111 checkForComodification();
112 throw new NoSuchElementException();
113 }
114 }
115
116 public int nextIndex() {
117 return cursor;
118 }
119
120 public int previousIndex() {
121 return cursor-1;
122 }
123
124 public void set(E e) {
125 if (lastRet < 0)
126 throw new IllegalStateException();
127 checkForComodification();
128
129 try {
130 AbstractList.this.set(lastRet, e);
131 expectedModCount = modCount;
132 } catch (IndexOutOfBoundsException ex) {
133 throw new ConcurrentModificationException();
134 }
135 }
136
137 public void add(E e) {
138 checkForComodification();
139
140 try {
141 int i = cursor;
142 AbstractList.this.add(i, e);
143 lastRet = -1;
144 cursor = i + 1;
145 expectedModCount = modCount;
146 } catch (IndexOutOfBoundsException ex) {
147 throw new ConcurrentModificationException();
148 }
149 }
150 }
151}
152
153
4.ArrayList<E>的实现
ArrayList<E>是List接口的具体实现子类，实现了List的所有接口，存储的数据是有序的，并且允许元素重复，以及null值的添加。每一个ArrayList实例都有一个容量。容量是用于存储列表中的元素的数组的大小。除此之外，该类是非线程同步的。
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
36
37
38
39
40
41
42
2 * Default initial capacity.默认的初始化容量
3 */
4 private static final int DEFAULT_CAPACITY = 10;
5
6 /**
7 * Shared empty array instance used for empty instances.
8 * 表示空集合
9 */
10 private static final Object[] EMPTY_ELEMENTDATA = {};
11
12 /**
13 * Shared empty array instance used for default sized empty instances. We
14 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
15 * first element is added.
16 * 空list集合元素，如果空集合，将此作为返回元素，表示是元素个数为0，不是集合为null。
17 * 此时，也有表示空构造方法调用默认的初始赋值。
18 */
19 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
20
21 /**
22 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
23 * will be expanded to DEFAULT_CAPACITY when the first element is added.
24 * 默认被赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当第一次添加元素时，会进行扩容
25 */
26 transient Object[] elementData; // non-private to simplify nested class access
27
28 //元素大小
29 private int size;
30
31 /**
32 * The maximum size of array to allocate.
33 * Some VMs reserve some header words in an array.
34 * Attempts to allocate larger arrays may result in
35 * OutOfMemoryError: Requested array size exceeds VM limit
36 * 最多允许存储的元素个数
37 */
38 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
39 //AbstractList中的变量，for fast-fail
40 protected transient int modCount = 0;
41
42
4.2 构造函数
关于Arrays和System参见 ：基本使用
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
2 if (initialCapacity > 0) {
3 this.elementData = new Object[initialCapacity];
4 } else if (initialCapacity == 0) {
5 //表示当前集合大小是0，当集合扩容时，扩容大小选择是 oldCapacity + (oldCapacity >> 1)
6 this.elementData = EMPTY_ELEMENTDATA;
7 } else {
8 throw new IllegalArgumentException("Illegal Capacity: "+
9 initialCapacity);
10 }
11}
12
13public ArrayList() {
14 //表示使用默认的构造函数，集合中的数组是空数组，集合扩容大小是 10
15 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
16}
17
18public ArrayList(Collection<? extends E> c) {
19 elementData = c.toArray();
20 if ((size = elementData.length) != 0) {
21 // c.toArray might (incorrectly) not return Object[] (see 6260652)
22 if (elementData.getClass() != Object[].class)
23 elementData = Arrays.copyOf(elementData, size, Object[].class);
24 } else {
25 // replace with empty array.
26 this.elementData = EMPTY_ELEMENTDATA;
27 }
28}
29
30
在构造函数中，有一个地方需要注意，EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA使用的区别。这两个常量都表示的是{}是Object类型的数组,他们这是两个不同的数组对象。对于这两个常量，有不同的作用，常量EMPTY_ELEMENTDATA纯粹表示的是集合中元素是null，集合中存储数据的elementData大小是0，如果需要添加元素，则需要按指定扩容规则扩容。DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示创建集合使用的是默认的构造方法，当第一次添加元素时，扩容的大小是采用默认的大小，就是10。关于扩容的，后面会详细讲解到，下面显示的是哪儿用到了DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
2
3
4
5
6
7
8
9
10
2 //elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA只有采用默认的构造方法成立
3 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
4 //在数组默认大小和要求最小之间选择较大的
5 return Math.max(DEFAULT_CAPACITY, minCapacity);
6 }
7 return minCapacity;
8}
9
10
4.3 基本方法
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
2
3public int size() {
4 return size;
5}
6
7public boolean isEmpty() {
8 return size == 0;
9}
10
11//集合中是否包含o元素，判断通过 o==null?e==null:o.equals(e);
12public boolean contains(Object o) {
13 return indexOf(o) >= 0;
14}
15//返回指定元素的下标，不存在返回-1，重写了父类方法
16public int indexOf(Object o) {
17 if (o == null) {
18 for (int i = 0; i < size; i++)
19 if (elementData[i]==null)
20 return i;
21 } else {
22 for (int i = 0; i < size; i++)
23 if (o.equals(elementData[i]))
24 return i;
25 }
26 return -1;
27}
28//如果a的size够大，存储到a中，否则创建一个新的数组返回
29public <T> T[] toArray(T[] a) {
30 if (a.length < size)
31 //创建一个新的数组返回，内容是 elementData
32 return (T[]) Arrays.copyOf(elementData, size, a.getClass());
33 //elementData元素拷贝到数组a中，从0开始，元素个数为size
34 System.arraycopy(elementData, 0, a, 0, size);
35 if (a.length > size)
36 a[size] = null;
37 return a;
38}
39
40//获取值，会进行范围检查
41public E get(int index) {
42 rangeCheck(index);
43
44 return elementData(index);
45}
46//范围检查
47private void rangeCheck(int index) {
48 if (index >= size)
49 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
50}
51
52
4.4 添加和修改元素
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
2public boolean add(E e) {
3 //会进行容量检查，modCount也会发生更改
4 ensureCapacityInternal(size + 1); // Increments modCount!!
5 elementData[size++] = e;
6 return true;
7}
8//指定位置添加元素，可知index及其以后的元素要后移一位
9public void add(int index, E element) {
10 rangeCheckForAdd(index);
11
12 ensureCapacityInternal(size + 1); // Increments modCount!!
13 //将下标index的元素和往后元素，拷贝到数组中，从index+1位置开始，长度是移动位数
14 System.arraycopy(elementData, index, elementData, index + 1,
15 size - index);
16 elementData[index] = element;//插入元素
17 size++;
18}
19//批量添加元素
20public boolean addAll(int index, Collection<? extends E> c) {
21 rangeCheckForAdd(index);
22
23 Object[] a = c.toArray();
24 int numNew = a.length;
25 ensureCapacityInternal(size + numNew); // Increments modCount
26
27 int numMoved = size - index;
28 if (numMoved > 0)
29 System.arraycopy(elementData, index, elementData, index + numNew,
30 numMoved);
31
32 System.arraycopy(a, 0, elementData, index, numNew);
33 size += numNew;
34 return numNew != 0;
35}
36
37
4.5 扩容
扩容主要是调用方法 ensureCapacityInternal(size + numNew); // Increments modCount，分析方法调用。集合是用的扩容是原size的1.5倍。
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
2 private void ensureCapacityInternal(int minCapacity) {
3 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
4 }
5
6 //区分是空集合，还是调用了默认的构造方法，如果是默认的构造方法，指定容量应该为10
7 private static int calculateCapacity(Object[] elementData, int minCapacity) {
8 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
9 return Math.max(DEFAULT_CAPACITY, minCapacity);
10 }
11 return minCapacity;
12 }
13
14 private void ensureExplicitCapacity(int minCapacity) {
15 modCount++;
16
17 // overflow-conscious code 扩容
18 if (minCapacity - elementData.length > 0)
19 grow(minCapacity);
20 }
21 //扩容函数
22 private void grow(int minCapacity) {
23 // overflow-conscious code
24 int oldCapacity = elementData.length;
25 int newCapacity = oldCapacity + (oldCapacity >> 1);//新元素的扩容大小
26 if (newCapacity - minCapacity < 0)//扩容后还不够，直接使用，要求的大小
27 newCapacity = minCapacity;
28 if (newCapacity - MAX_ARRAY_SIZE > 0)//检测是否找过int最大值
29 newCapacity = hugeCapacity(minCapacity);
30 // minCapacity is usually close to size, so this is a win:
31 elementData = Arrays.copyOf(elementData, newCapacity);//复制元素到新的数组中
32 }
33
34 private static int hugeCapacity(int minCapacity) {
35 if (minCapacity < 0) // overflow
36 throw new OutOfMemoryError();
37 return (minCapacity > MAX_ARRAY_SIZE) ?
38 Integer.MAX_VALUE :
39 MAX_ARRAY_SIZE;
40 }
41
42
4.7 删除元素
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
2 //将index+1及其之后的元素，复制到index位置
3 public E remove(int index) {
4 rangeCheck(index);
5
6 modCount++;
7 E oldValue = elementData(index);
8
9 int numMoved = size - index - 1;
10 if (numMoved > 0)
11 System.arraycopy(elementData, index+1, elementData, index,
12 numMoved);
13 //尾元素需要被回收
14 elementData[--size] = null; // clear to let GC do its work
15
16 return oldValue;
17 }
18 //自行分析
19 private void fastRemove(int index) {
20 modCount++;
21 int numMoved = size - index - 1;
22 if (numMoved > 0)
23 System.arraycopy(elementData, index+1, elementData, index,
24 numMoved);
25 elementData[--size] = null; // clear to let GC do its work
26 }
27
28 /*** 批量删除 ***/
29 //将集合中c的元素删除
30 public boolean removeAll(Collection<?> c) {
31 Objects.requireNonNull(c);
32 return batchRemove(c, false);
33 }
34 //将非集合c中的元素移除
35 public boolean retainAll(Collection<?> c) {
36 Objects.requireNonNull(c);
37 return batchRemove(c, true);
38 }
39 //批量删除
40 private boolean batchRemove(Collection<?> c, boolean complement) {
41 final Object[] elementData = this.elementData;
42 int r = 0, w = 0;
43 boolean modified = false;
44 try {
45 for (; r < size; r++)
46 //complement为false，则是移除元素调用的，elementData[w++]存储的是不在数组中元素
47 //complement为false，则是保留元素调用的，elementData[w++]存储的是在数组中的元素
48 if (c.contains(elementData[r]) == complement)
49 elementData[w++] = elementData[r];
50 } finally {
51 // Preserve behavioral compatibility with AbstractCollection,
52 // even if c.contains() throws.
53 if (r != size) {
54 System.arraycopy(elementData, r,
55 elementData, w,
56 size - r);
57 w += size - r;
58 }
59
60 //让GC工作，回收空闲位置
61 if (w != size) {
62 for (int i = w; i < size; i++)
63 elementData[i] = null;
64 modCount += size - w;
65 size = w;
66 modified = true;
67 }
68 }
69 return modified;
70 }
71
72
4.8 迭代元素
都是采用的迭代器的设计模式，实现思路和AbstractList的iterator()方法一样，可以参看以前的实现博客。
2
3
4
5
6
7
8
9
10
2 public ListIterator<E> listIterator() {
3 return new ListItr(0);
4 }
5
6 public Iterator<E> iterator() {
7 return new Itr();
8 }
9
10
2
3
2
3
5. 补充内容： RandomAccess 接口
2
3
4
5
2
3}
4
5
RandomAccess是一个空接口，这种空接口是起标识作用的，标识实现了这个接口的类具有随机访问功能。
在Collections.binarySearch（）方法中，它要判断传入的list是否是RamdomAccess 的实例，如果是，调用indexedBinarySearch（）方法，如果不是，那么调用iteratorBinarySearch（）方法。
为什么要这样做：
RandomAccess 的实例是支持随机访问的，通过下标获取元素的值复杂度是O(1) , 所以ArrayList实现了随机访问接口，根据下标获取的元素。但是对于LinkedList，他也是List的子类，也具有get(index)方法，但是这种获取的复杂度确实O(n)（是通过遍历元素，直到第index个元素），所以如果排序的时候，通过get获取元素比较，则时间复杂度太大。
2
3
4
5
6
7
8
9
10
11
2 int binarySearch(List<? extends Comparable<? super T>> list, T key) {
3 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
4 //RandomAccess实例，通过下标获取元素比较。
5 return Collections.indexedBinarySearch(list, key);
6 else
7 //不支持随机访问，则通过迭代获取元素进行比较。
8 return Collections.iteratorBinarySearch(list, key);
9 }
10
11
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
2private static <T>
3 int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
4 int low = 0;
5 int high = list.size()-1;
6
7 while (low <= high) {
8 int mid = (low + high) >>> 1;
9 Comparable<? super T> midVal = list.get(mid);
10 int cmp = midVal.compareTo(key);
11
12 if (cmp < 0)
13 low = mid + 1;
14 else if (cmp > 0)
15 high = mid - 1;
16 else
17 return mid; // key found
18 }
19 return -(low + 1); // key not found
20 }
21
22 //不支持随机访问，为避免get()查找浪费，使用ListIterator从头开始查找中间元素
23 private static <T>
24 int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
25 {
26 int low = 0;
27 int high = list.size()-1;
28 ListIterator<? extends Comparable<? super T>> i = list.listIterator();
29
30 while (low <= high) {
31 int mid = (low + high) >>> 1;
32 Comparable<? super T> midVal = get(i, mid);
33 int cmp = midVal.compareTo(key);
34
35 if (cmp < 0)
36 low = mid + 1;
37 else if (cmp > 0)
38 high = mid - 1;
39 else
40 return mid; // key found
41 }
42 return -(low + 1); // key not found
43 }
44
45 /**
46 * Gets the ith element from the given list by repositioning the specified
47 * list listIterator.
48 */
49 private static <T> T get(ListIterator<? extends T> i, int index) {
50 T obj = null;
51 int pos = i.nextIndex();
52 if (pos <= index) {
53 do {
54 obj = i.next();
55 } while (pos++ < index);
56 } else {
57 do {
58 obj = i.previous();
59 } while (--pos > index);
60 }
61 return obj;
62 }
63
64
总结List遍历方式的选择：
-
实现了RandomAccess接口的list，可以通过普通for循环，其次是foreach。
-
未实现RandomAccess 接口的list，通过迭代器去遍历，或者foreach（也是迭代器），但不可通过for，思考复杂度是O(n
2),思考原因 ?
