本文若无特殊说明，源码均为JDK1.8
list中常用的主要有ArrayList和Linkedlist,其中Vector，Stack并不常用。下图为List的框架图：
根据上图，逐个来看其各个类、接口：
Collection：是根接口，其源码没有任何的实现，都是由其子类去实现。
AbstractCollection：实现了Collection接口，要实现一个不可修改的collection，只需扩展此类，并提供 iterator和size 方法的实现。但要实现可修改的collection，就必须另外重写此类的 add 方法（否则，会抛出 UnsupportedOperationException），iterator 方法返回的迭代器还必须另外实现其 remove 方法。
Iterator：迭代器。
ListIterator：系列表迭代器，允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。
List：继承于Collection的接口。它代表着有序的队列
AbstractList：List 接口的主要实现
Queue：队列。提供队列基本的插入、获取、检查操作。
Deque：一个线性 collection，支持在两端插入和移除元素。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。
AbstractSequentialList：提供了 List 接口的骨干实现，从而最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作。从某种意义上说，此类与在列表的列表迭代器上实现“随机访问”方法。
LinkedList：List接口的链接列表实现。它实现所有可选的列表操作
ArrayList：List接口的大小可变数组的实现。它实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。
Vector：实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。
Stack：后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈
Enumeration：枚举，实现了该接口的对象，它生成一系列元素，一次生成一个。连续调用 nextElement 方法将返回一系列的连续元素。
ArrayList解析
AraayList概述
ArrayList是实现List接口的动态数组，所谓动态就是它的大小是可变的。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。
每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。默认初始容量为10。随着ArrayList中元素的增加，它的容量也会不断的自动增长。在每次添加新的元素时，ArrayList都会检查是否需要进行扩容操作，扩容操作带来数据向新数组的重新拷贝，所以如果我们知道具体业务数据量，在构造ArrayList时可以给ArrayList指定一个初始容量，这样就会减少扩容时数据的拷贝问题。当然在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。
需要注意的是ArrayList不是线程安全的，在多线程环境下需要同步操作，最好是在创建的时候进行同步：
List list = Collection.synchronizedList(new ArrayList())
ArrayList源码
ArrayList实现的List接口，底层采用数组实现，所以基本上也就是对数组进行操作。
1. 底层采用数组实现
transient Object[] elementData;
我们可以发现有个transient关键字，它是变量修饰符，如果用它修饰一个实例变量，当对象存储时，它的值不需要维持，
一个对象只要实现的Serilizable接口，这个对象就可以被序列化，然而在实际开发过程中，有些类的属性不需要序列化，那么就可以用transient修饰
但是transient不能修饰类和方法，静态变量不管是否被transient修饰，都不能序列化
在Java中，对象的序列化可以通过实现两种接口来实现，若实现的是Serializable接口，则所有的序列化将会自动进行，
若实现的是Externalizable接口，则没有任何东西可以自动序列化，需要在writeExternal方法中进行手工指定所要序列化的变量，这与是否被transient修饰无关
这里的Object[] elementData就是ArrayList的容器，下面的介绍都是基于elementData变量来操作的
2. 构造函数
/**
* Constructs an empty list with an initial capacity of ten.
* 构造一个初始容量为 10 的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs an empty list with the specified initial capacity.
* 构造一个指定初始容量的空列表
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* 构造一个包含指定 collection 的元素的列表，
* 这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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;
}
}
3. 新增操作
ArrayList提供了add(E e)，add(int index, E element)，addAll(Collection<? extends E> c)，addAll(int index, Collection<? extends E> c)，set(int index, E element)这5个方法来实现新增操作。
- add(E e) 将指定的元素添加到此列表的尾部
/**
* Appends the specified element to the end of this list.
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
这里的ensureCapacityInternal()方法是对ArrayList进行扩容，elementData(size++) = e，将列表末尾元素指向e。
- add(int index, E 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).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}
这里有个System.arraycopy()方法，该方法主要作用就是将index位置空出来以供新数据插入，这里需要进行数组数据的右移，这是非常麻烦和耗时的，所以如果指定的数据集合需要进行大量插入（中间插入）操作，推荐使用LinkedList。
- addAll(Collection<? extends E> c) 将该Collection中的所有元素添加到此列表的尾部，按照指定Collection的迭代器返回元素顺序
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
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;
}
这里同样也用了System.arraycopy()方法，我们来看看此方法
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
就是进行数组元素的复制。即从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。将源数组src从srcPos位置开始复制到dest数组中，复制长度为length，数据从dest的destPos位置开始粘贴。
- addAll(int index, Collection<? extends E> c) 从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
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;
}
- set(int index, E element) 用指定的元素替代此列表中指定位置上的元素。
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
4. 删除操作
ArrayList提供了remove(int index)，remove(Object o)，removeRange(int fromIndex, int toIndex)，removeAll(Collection<?> c)四个方法进行元素的删除
- remove(int index) 移除此列表中指定位置上的元素。
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//位置验证
rangeCheck(index);
modCount++;
//需要删除的元素
E oldValue = elementData(index);
//向左移动的位数
int numMoved = size - index - 1;
////若需要移动，则想左移动numMoved位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//置空最后一个元素
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
- remove(Object o) 移除此列表中首次出现的指定元素（如果存在）
/**
* 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
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
//进行null判断，ArrayList允许null存在
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;
}
- removeRange(int fromIndex, int toIndex) 移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
- removeAll(Collection<?> c) 是继承自AbstractCollection的方法，ArrayList本身并没有提供实现。
/**
* {@inheritDoc}
*
* <p>This implementation iterates over this collection, checking each
* element returned by the iterator in turn to see if it's contained
* in the specified collection. If it's so contained, it's removed from
* this collection with the iterator's <tt>remove</tt> method.
*
* <p>Note that this implementation will throw an
* <tt>UnsupportedOperationException</tt> if the iterator returned by the
* <tt>iterator</tt> method does not implement the <tt>remove</tt> method
* and this collection contains one or more elements in common with the
* specified collection.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*
* @see #remove(Object)
* @see #contains(Object)
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
5. 查找操作
ArrayList提供了get(int index)用读取ArrayList中的元素。由于ArrayList是动态数组，所以我们完全可以根据下标来获取ArrayList中的元素，而且速度还比较快，故ArrayList长于随机访问。
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
6. 扩容操作
在上面的新增操作中都存在这样一个方法：，其主要作用就是扩容
在JDK1.7中的扩容方法为ensureCapacity()
public void ensureCapacity(int minCapacity) {
//修改计时器
modCount++;
//ArrayList容量大小
int oldCapacity = elementData.length;
/*
* 若当前需要的长度大于当前数组的长度时，进行扩容操作
*/
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
//计算新的容量大小，为当前容量的1.5倍
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//数组拷贝，生成新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
JDK1.8中的扩容方法ensureCapacityInternal()，最终还是靠grow()方法来扩容的
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);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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 :
不管是在JDK1.8还是在JDK1.7中，扩容都是1.5倍，为什么是1.5倍了，扩容太大倍数容易造成内存的浪费，扩容太小需要多次对数组进行分配内存，性能消耗比较严重，所以1.5倍是最好的的倍数。
另外ArrayList还提供了一个方法将底层数组的容量调整为当前列表保存的实际元素的大小的功能，它可以通过trimToSize()方法来实现。该方法可以最小化ArrayList实例的存储量。
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}