List是常用的数据类型，用来存储一组有序的数据，常用的实现有ArrayList和LinkedList。
ArrayList
Members
ArrayList内部通过数组实现，用size记录当前list的大小，所以随即访问就是先检查index，然后返回数组元素O(1)。
// transient 表示序列化时，不包含该字段
transient Object[] elementData; // non-private to simplify nested class access
private int size;
Add
在任意位置添加一个元素时，会复制剩下的元素，效率较低。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity); // 若一开始是空list，返回新容量和10中较大的
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 最小容量比当前数组大，则扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
Remove
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;
}
LinkedList
Members
LinkedList内部通过一个双向链表实现。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Get
get任意位置的元素，是通过链表遍历实现的，如果是前1/2从头开始遍历，后则从尾遍历。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Add
如果只是加在最前/后的位置，则简单link即可，若任意位置则需先找到该节点位置，然后link。
public void addFirst(E e) {
linkFirst(e);
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Remove
remove也是基于链表的操作，十分简单，时间复杂度O(1)，如果要删除任意位置的话，需要先找到这个节点O(n)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
modCount
注意到在这两种list操作中都有modCount的存在，它是定义在AbstractList中的，作用是支持 fail-fast iterators。它是可选的，子类并不一定需要支持它，如果需要则需要在add/remove操作时对这个数值+1。
原理是调用list.iterator();时返回一个Iterator对象，该对象会使用list当前的modCount初始化一个expectedModCount，然后在Iterator对象的后续操作，都会先去检测expectedModCount是否与当前list最新的modCount一致，不一致则会抛出ConcurrentModificationException。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
comments powered by