一、java.util.ArrayList
1.1 ArrayList 继承结构
ArrayList实现了RandomAccess，可以随机访问（其实就是通过数组下标访问）；实现了Cloneable，可以拷贝（通过System.arraycopy方法实现）；实现了Serializable，可以进行序列化，能被序列化传输。
ArrayList非线程安全。
1.2 ArrayList 属性
private static final long serialVersionUID = 8683452581122892189L;
// 初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 共享空的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 共享一个具有初始化容量的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 核心数组
transient Object[] elementData; // non-private to simplify nested class access
// 数组存放元素总数
private int size;
1.3 ArrayList 方法
// 确保Capacity能达到指定的minCapacity
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY; if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
} private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
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 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容为之前的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
} private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
上面是ensureCapacity方法，确保Capacity能大于等于minCapacity。ArrayList每次扩容为之前的1.5倍。
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
拷贝ArrayList方法，这也不是一种深度拷贝，只是将源数组的内容拷贝到新数组，元素并未重建（拷贝）。
public void add(int index, E element) {
rangeCheckForAdd(index);
// 确保容量足够
ensureCapacityInternal(size + 1); // Increments modCount !!
// 将index及其后元素统统向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
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;
}
ArrayList其根本是个数组，因此在数组末尾增删元素是很高效的。但是要在中间增删元素，就必须移动后面的所有元素，效率肯定会有影响。
如果需要频繁向中间增删元素还是LinkedList比较合适。
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某个value，找到第一个value之后，就删除并return。
// 将ArrayList写入到ObjectOutputStream
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
// 将非静态和非transient字段写入流
s.defaultWriteObject(); // 将size写入流
s.writeInt(size); // 将所有的元素写入流中
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
} if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
} private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA; // 从流中读入非静态和非transient字段
// Read in size, and any hidden stuff
s.defaultReadObject(); // 读入size
s.readInt(); // ignored if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size); Object[] a = elementData;
// Read in all elements in the proper order.
// 读取元素
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
这两个方法将ArrayList写入流或者从流中读入。但是我有个疑问，都是private方法，这个写出来谁能调用？
二、java.util.Vector
2.1 Vector 继承结构
Vector继承结构和ArrayList相同。ArrayList是非线程安全的，与之对应的Vector是线程安全的。
2.2 Vector 属性
// 存储对象的数组
protected Object[] elementData;
// 可以理解为Vector的capacity，也可以理解为数组的length
protected int elementCount;
// 可以自定义capacity扩容量
protected int capacityIncrement;
private static final long serialVersionUID = -2767605614048989439L;
2.3 Vector 方法
扩容方法
public synchronized void ensureCapacity(int minCapacity) {
if (minCapacity > 0) {
// 注意这里会导致modCount++ !!
modCount++;
ensureCapacityHelper(minCapacity);
}
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// 需要扩容处理
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 如果没有自定义扩容增量capacityIncrement，则直接扩容为之前的容量的两倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
// 扩容为之前容量的两倍如果还不够，则直接扩容为minCapacity
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;
}
ensureCapacity方法加了synchronized同步锁。在扩容策略上跟ArrayList稍有不同，ArrayList默认扩容为之前容量的1.5倍，而Vector则默认扩容为之前容量的2倍。除此之外Vector还允许自定义扩容增量。
public synchronized List<E> subList(int fromIndex, int toIndex) {
return Collections.synchronizedList(super.subList(fromIndex, toIndex),
this);
}
在subList方法中，为了返回一个线程安全的List，加上了Collections.synchronizedList封装。
If you need synchronization, a Vector will be slightly faster than an ArrayList synchronized with Collections.synchronizedList.
Collections.synchronizedList封装是对List对象添加同步锁，各方法本质上还是调用的List的方法。
Vector类其他方法和ArrayList差不多，无非加上了一个synchronized同步处理，这里就不再赘述了。
三、java.util.LinkedList
3.1 LinkedList继承结构
LinkedList没有实现RandomAccess interface，可见其并不具备随机访问特性，毕竟是链表。
LinkedList同样是非线程安全的。
LinkedList比较适合从中间删除、添加元素的场景；ArrayList则更适合只在末尾增删元素，遍历的场景。
3.2 LinkedList 属性
transient int size = 0;
// 指向第一个节点
transient Node<E> first;
// 指向最后一个节点
transient Node<E> last;
其中Node类为：
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;
}
}
Node节点包含next和prev两个指针，分别指向前面和后面的一个节点。
3.3 LinkedList 方法
public E set(int index, E element) {
// 检查index是否在范围内
checkElementIndex(index);
// 找出这个node节点
Node<E> x = node(index);
// 保存旧的值
E oldVal = x.item;
// 更新值
x.item = element;
return oldVal;
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果index指向链表前半部分，则从前向后遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// index指向链表的后半部分，从后往前遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
在这个set方法中，有个参数是index，修改指定index上的元素内容，但链表本身是不具备index属性的，为此通过node()方法遍历（从first向last方向开始计数）找到第index个Node，即为需要修改的节点。
node方法为了提高效率，根据index所指向的位置，从前向后或从后向前遍历，因此最多遍历size/2个节点就可以找到index节点了。
// 获取第一个节点内容，但是不删除
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
} // 获取第一个节点内容并且删除之
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
} // 删除第一个节点并返回其内容，跟poll一样
public E pop() {
return removeFirst();
} // 添加一个元素到结尾
public boolean offer(E e) {
return add(e);
} // 添加一个元素到开头
public void push(E e) {
addFirst(e);
}
上面是几个比较容易混淆的方法，其实看下代码就明白了。
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
LinkedList提供了一个反向迭代器，因为LinkedList本身就是一个双向链表，反向遍历也是很方便的。
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
拷贝方法，同样是浅拷贝，每个节点的元素内容并没有被拷贝。拷贝出来的结果是两个链表都引用的同一个元素内容。