private static final int DEFAULT_CAPACITY = 10; // 初始默认容量为10
transient Object[] elementData; // 存放元素的数组
private int size; // 这个值是实际数组包含元素的数量, 注意这个值不是数组的大小
private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组
1
2
3
4
无参的构造方法
源码注释: Constructs an empty list with an initial capacity of ten.(构造初始容量为10的列表);
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1
2
3
创建初始容量的构造方法
源码注释:Constructs an empty list with the specified initial capacity.(构造指定容量的列表);
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
1
2
3
4
5
6
7
8
9
10
创建指定集合的列表
源码注释:Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.(构造一个指定的collection集合的列表, 安装collection 迭代器返回的顺序);
源码分析:参数 c 调用toArray()方法转换为数组赋给列表的属性elementData ,
如果集合 c 元素为0, 则创建默认容量为空的列表;
如果c > 0, 则判断类型, 再复制数组,此处具有填充的效果
源码注释: Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).(删除指定索引的元素, 并且所有元素左移)
源码分析: 删除指定位置的元素,先检查下标再获取此元素; 最后调用 System 类中的arraycopy()方法把除去index位置的元素的其他元素全部左移,最后一个元素 elementData[–size] = null;最终数组的大小不变只是末尾的一个元素置为null
最终结果就像这样
public static native void arraycopy(Object src, int srcPos, dest, int destPos, length);
1
public E remove(int index) {
rangeCheck(index);
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;
}
1
2
3
4
5
6
7
8
9
10
4.删除指定元素,首次出现的元素 remove(object)
源码注释: Removes the first occurrence of the specified element from this list, if it is present. If the list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists). Returns true if this list contained the specified element (or equivalently, if this list changed as a result of the call).
条件: (o == null ? get(i) == null : o.equals(get(i))), 移除首次出现的指定元素,
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;
}
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
}
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
5.修改元素 set(index, element)
源码注释: Replaces the element at the specified position in this list with the specified element.(替换指定位置的元素)
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
1
2
3
4
5
6
7
以上5个操作是基本的crud操作, 下面要探讨List的其他操作
6.添加元素到指定位置 add(index, element)
源码注释: Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).(添加元素到指定索引, 如果不是添加到最后的位置, 则右边的元素全部右移)
源码注释: Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.
(返回第一次出现此元素的索引, 如果没有找到此元素, 返回 -1)
**源码分析:**这里的算法和 remove(object) 方法一样,
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData))
return i;
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
10.搜索最后出现此元素的索引 lastIndexOf(object)
源码注释: Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the highest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.
(返回最后一次出现此元素的索引, 如果列表不包含此元素, 返回 -1)
源码解析: 此处是从后往前遍历的循环, 逻辑是 indexOf() 方法的对立;
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData))
return i;
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
11.判断是否包含指定元素 contains(object)
源码注释: Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o == null ? e==null : o.equals(e)).(如果列表包含此元素, 则返回 true 否则 false)
**源码注释:**Removes all of the elements from this list. The list will be empty after this call returns.(从此列表中删除所有元素。 此调用返回后，列表将为空)
源码分析: for循环把数组所有引用置空, size = 0
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData = null;
size = 0;
}
1
2
3
4
5
6
7
13.list 转数组 toArray()
源码注释: Returns an array containing all of the elements in this list in proper sequence (from first to last element).
The returned array will be “safe” in that no references to it are maintained by this list. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.
This method acts as bridge between array-based and collection-based APIs.
(返回一个包含列表所有元素的新的数组)
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
1
2
3
14.list 转 toArray(T[] a)
源码注释: Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.
If the list fits in the specified array with room to spare (i.e., the array has more elements than the list), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of the list only if the caller knows that the list does not contain any null elements.)
(把列表所有元素复制到给的数组中, 如果给定的数组大于列表长度, 多出的部分分配null)
public Iterator<E> iterator() {
return new Itr();
}
1
2
3
2) 获取列表迭代器 listIterator()
public ListIterator<E> listIterator() {
return new ListItr(0);
}
1
2
3
3) 获取从指定位置开始的列表迭代器 listIterator(index)
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
1
2
3
4
5
ArrayList 里有两个内部类 Itr 和 ListItr
关系图:
4) Itr 实现 Iterator 源码分析
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
.......... 忽略下面代码
}
1
2
3
4
5
6
字段说明:
int cursor; //下一元素的索引, 当迭代时, 执行一次 next()方法 cursor++,
当 cursor == size 和列表长度相等时即没有下一个元素;
int lastRet = -1; //最后一个元素的索引, 调用 next()方法时被重新赋值 lastRet = i;
public E next() {
checkForComodification();
int i = cursor; // 初始化为1, i = 1,
// 如果没有调用 hasNext()方法直接调用next()方法获取元素有可能导致索引越界的异常
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
// 检查列表是否被修改过, add、set、remove 等操作都会导致modCount的值发生改变
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
移除上一次调用next()方法返回的元素 remove()
源码注释: Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.
(在每次调用next()方法是, 只能调用一次此方法)
奈斯