ArrayList
-
介绍
ArrayList是基于动态数组的数据结构
ArrayList 随机访问速度快，中间插入与删除速度慢，尾部插入与删除速度也快。
重要属性
//存储元素的数组缓冲区
transient Object[] elementData;
//List的大小
private int size;
- 构造函数一
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);
}
}
此构造需要传入一个初始化容量initialCapacity；
如果大于0，则创建此大小的数组缓冲区，等于0，则直接使用一个空数组EMPTY_ELEMENTDATA
因此，使用ArrayList的时候如果预先知道其容量，使用此构造方法传入容量，避免内存浪费与add时触发无必要的扩容。
- 构造函数二
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
此构造直接使用一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA作为数据缓冲区，add时才扩容。
- 构造函数三
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
此构造直接使用传入集合c数组数据作为数据缓冲区。
- get方法
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
通过index直接从数组缓冲区中获取数据，根据下标取数据快。
- set方法
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
直接从数组缓冲区替换指定index的数据，速度快。
- add方法
public boolean add(E e) {
//确保内部容量够用
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY = 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//真正扩容数组缓冲区
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// a >> 1 相当于 a / 2^1 取整
// a >> 2 相当于 a / 2^2 取整
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
举例说明一下扩容：
`假设当前数组缓冲区大小为10，ArrayList.size也为10，`
`=> add(ele)`
`=> ensureCapacityInternal(11) // size+1 = 11`
`=> ensureExplicitCapacity(11)`
`=> grow(minCapacity = 11)`
`=> oldCapacity = elementData.length = 10`
`newCapacity = oldCapacity + (oldCapacity >> 1) = 15`
`...这块未影响newCapacity的值`
`elementData = Arrays.copyOf(elementData, newCapacity)，此时elementData.length = newCapacity = 15了`
`=>elementData[10] = ele;// size++ 先使后加`
add如果不触发扩容的话速度非常快，触发扩容需要数组copy，速度会受到影响
- add方法(从指定index add)
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//确保数组容量够用
ensureCapacityInternal(size + 1);
//将数组缓冲区中index之后的数据，向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
此方法相比在上一add方法，多一步数组拷贝过程。
- remove方法(通过index)，返回旧的数据
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
//取出当前index之前的值，下面作为方法返回值
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
//大于0，说明不是移除最后一个元素，需要将index之后的数据往前移一位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//最后一个一定没用了，置为空，让gc去管
elementData[--size] = null;
return oldValue;
}
如果是移除最后一个元素的话，不涉及数组copy，速度很快；
如果移除非最后一个元素，需要数组copy，速度会受影响。
- remove方法(通过元素)，返回是否移除前是否包含该元素
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
}
遍历元素，找到与传入元素相等的元素的index，然后移除(过程与上面通过index remove的过程相同)；
注意：如果元素中包含重复的元素，则仅移除前面的那个元素(因为是从前往后找index的);
- addAll方法
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(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;
}
addAll 跟上面add方法基本一样。
- removeAll方法
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//complement=false
//如果c不包含elementData[r],把elementData[r]保留
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// 看上面的for循环，没有多线程并发问题的话，r一定是等于size的，
// 这个if不会命中
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//如果不是全部移除，w肯定不等于size，
//这个if命中，把多余的元素置空
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;
}
举例分析以下代码：
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> c = new ArrayList<>(Arrays.asList(1, 3, 5));
list.removeAll(c);
System.out.println(list);// 输出[2, 4, 6, 7]
1.原始数据
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | _ | _ | _ |
|---|
2.batchRemove == for循环完后=>
| 2 | 4 | 6 | 7 | 5 | 6 | 7 | _ | _ | _ |
|---|
3.置空多余元素
| 2 | 4 | 6 | 7 | _ | _ | _ | _ | _ | _ |
|---|
- subList(int fromIndex, int toIndex)
public List<E> subList(int fromIndex, int toIndex) {
//检查index是否异常
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
//......
ArrayList.this.elementData[offset + index] = e;
//......
}
public E get(int index) {
//......
return (E) ArrayList.this.elementData[offset + index];
}
public void add(int index, E e) {
//......
parent.add(parentOffset + index, e);
//......
}
public E remove(int index) {
//......
E result = parent.remove(parentOffset + index);
//......
}
protected void removeRange(int fromIndex, int toIndex) {
//......
parent.removeRange(parentOffset + fromIndex, parentOffset + toIndex);
//......
}
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//......
parent.addAll(parentOffset + index, c);
//......
}
//......
}
该方法返回的不是ArrayList，而是SubList;
SubList相当于是原ArrayList的一个映射，[fromIndex, toIndex);
子list实际上是修改的父ArrayList。
父list操作后，子list再操作会抛出异常 ConcurrentModificationException，是因为父list操作后不会把modCount同步给子list。
- clear方法
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
遍历将数组缓冲区全部置空，size置0。
