基础结构

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
// 默认初始化容量,私有常量
private static final int DEFAULT_CAPACITY = 10;

// 初始容量设为0时的数组,私有常量
private static final Object[] EMPTY_ELEMENTDATA = {};

// 未设置初始容量时的空数组,与上一步拆分以在第一个元素添加时确定数组大小,私有常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存放数据,如果 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA,那么第一个数据时,容量为默认容量10
transient Object[] elementData; // non-private to simplify nested class access

// 元素个数
private int size;

// 设定初始数量的构造函数
public ArrayList(int initialCapacity) {
// 传入容量>0,定义一个length为传入容量的数据
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
// 传入容量为0,定义为EMPTY_ELEMENTDATA
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}

// 未设定容量,设定为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 从现成容器创建list
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

ArrayList核心方法,Arrays.copyOf()

ArrayList的核心其实就是通过调用Arrays.copyOf()方法,将要移动的数据复制到指定位置上。实现数组的增删

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 复制指定长度的数组
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}

// 复制指定长度的数组,如果复制的长度小于original的length会进行剪切
// 而如果复制到长度大于original的length,多余的位置会填充为null
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
// 创建对应类型的数组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// original从0开始复制到copy数组中。copy数组从0开始填充。长度为original.length和newLength中更小的一个
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}

// 系统native方法,会将src从srcPos开始的length长度的数据复制到dest数组destPos开始的位置
// 即从srcPos - (srcPos+length-1)的数据会被复制到dest - (dest + length - 1)
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);

常用方法

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
// 最小化实例数组的存储
public void trimToSize() {
modCount++;
// 如果数据能收缩,则修剪实例
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
// native方法,复制数组
: Arrays.copyOf(elementData, size);
}
}

// 如有必要,对数组进行扩容
public void ensureCapacity(int minCapacity) {
// 如果是不含数据且未设置初始容量的list,最小期望值为默认值10,否则为0
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
// 如果传入容量>最小期望值则扩容
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是第一次插入元素且没有设置初始容量,则按照默认容量和需求容量中最大的一个元素扩容
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

// 扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果期望的容量大于当前数组长度才扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

// 数组最大长度,-8是为了给jvm的数据会占用一部分空间
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 数组扩容,保证能容纳传入的容量
private void grow(int minCapacity) {
// 获取当前数组长度
int oldCapacity = elementData.length;
// 增加oldCapacity>>1,就是原容量的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果计算结果小于预期容量,则按照预期容量扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果预定扩容容量大于最大容量,则判断预定期望值是否大于最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

// 从前往后遍历数组,如果o为null则返回第一个null的小标,否则根据equals()返回第一个相等下标,不含有则返回-1
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;
}

// 转化为数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}

// 返回传入类型的数组,如果传入数组长度<size,创建一个新数组返回,否则会将元素复制到传入数组中
// 如果传入数组长度>size,会将原数组最后一个元素的下一位置设为null,用于在原数组全不为null是确定长度
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

// 通过下标访问数组
E elementData(int index) {
return (E) elementData[index];
}

// 检查访问是否越界
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// add或者addAll检查是否越界,和rangeCheck()不同的在于可以=size
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

get - 获取list数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 先检查下标是否越界,再根据数组访问
public E get(int index) {
// 检查是否越界
rangeCheck(index);
// 根据下标访问数组
return elementData(index);
}

// 先扩容,再在数据尾部设置
public boolean add(E e) {
// 数组扩容,最小容量为size+1
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

list插入数据

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
// 替换对应下标的数据
public E set(int index, E element) {
// 检查是否越界
rangeCheck(index);

// 替换元素并返回原值
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

// 固定位置插入元素
public void add(int index, E element) {
// 检查是否越界,与get的越界检查不同的是,add可以插入在size位置上
rangeCheckForAdd(index);
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 调用native方法将原index开始的数据复制到index+1后
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 插入元素
elementData[index] = element;
size++;
}

// 将容器元素加入list
public boolean addAll(Collection<? extends E> c) {
// 将容器转为数组
Object[] a = c.toArray();
int numNew = a.length;
// 扩容到至少能容纳原容量+容器容量大小的数组
ensureCapacityInternal(size + numNew); // Increments modCount
// 将容器的数组添加到list后
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

// 固定位置插入容器的所有数据,原理相似
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(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;
}

remove - 删除list元素

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
// 移除下标处元素
public E remove(int index) {
// 检查是否越界
rangeCheck(index);
// 结构修改次数+1
modCount++;
E oldValue = elementData(index);
// 计算出需要移动的元素数量
int numMoved = size - index - 1;
// 如果删除的是最后一位,就不需要进行复制了
if (numMoved > 0)
// 通过复制将待删除元素的后续元素前移一位
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
// 清除引用
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}

// 和indexOf相似,从前往后遍历查找value第一次出现的位置,进行删除
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;
}

// 和remove相似,先复制后续元素,然后清空最后一位引用
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}

// 删除从fromIndex到toIndex的数据
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
// 计算需要移动的元素数量(从toIndex到末尾)
int numMoved = size - toIndex;
// 将toIndex开始的元素直接移动到fromIndex处
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);

// 清除多余位置的引用,方便垃圾回收
int newSize = size - (toIndex - fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}

// 删除所有属于c的元素
public boolean removeAll(Collection<?> c) {
// 需要c不为null
Objects.requireNonNull(c);
return batchRemove(c, false);
}

// 删除所有属于c的元素
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}

// 并查集删除
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
// 属于或者不属于标志,删除属于c的元素则为false,删除不属于c的元素则为true
boolean modified = false;
try {
// 遍历数组
for (; r < size; r++)
// 根据complement判断是删除属于c的元素还是不属于c的元素
if (c.contains(elementData[r]) == complement)
// 双指针删除,拿删除属于c的元素举例,这时complement为false
// 如果比较结果为true,则元素不属于c,将这个元素放入到w的位置,然后w++,否则不操作
elementData[w++] = elementData[r];
} finally {
// 如果抛出异常,将未处理元素复制到已处理元素后
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// 处理完所有元素后对后续位置清空引用
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}