一、介绍
先回顾一下List的框架图
由图中的继承关系，可以知道，ArrayList、LinkedList、Vector、Stack都是List的四个实现类。 AbstractList是一个抽象类，它继承于AbstractCollection。AbstractList实现List接口中除size()、get(int location)之外的函数。
AbstractSequentialList 是一个抽象类，它继承于AbstractList。AbstractSequentialList 实现了“链表中，根据index索引值操作链表的全部函数”。
ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。
- LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率低。
- Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。
Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。
二、性能测试
在对ArrayList、LinkedList、Vector、Stack进行比较之前，我们先来对他们进行一个性能测试，结合源码和测试结果来对ArrayList、LinkedList、Vector、Stack进行详细的分析。
import java.util.*;public class ListTest { private static final int COUNT = 100000; private static LinkedList linkedList = new LinkedList(); private static ArrayList arrayList = new ArrayList(); private static Vector vector = new Vector(); private static Stack stack = new Stack(); public static void main(String[] args) { // 换行符 System.out.println(); // 插入 insertByPosition(stack) ; insertByPosition(vector) ; insertByPosition(linkedList) ; insertByPosition(arrayList) ; // 换行符 System.out.println(); // 随机读取 readByPosition(stack); readByPosition(vector); readByPosition(linkedList); readByPosition(arrayList); // 换行符 System.out.println(); // 删除 deleteByPosition(stack); deleteByPosition(vector); deleteByPosition(linkedList); deleteByPosition(arrayList); } // 获取list的名称 private static String getListName(List list) { if (list instanceof LinkedList) { return "LinkedList"; } else if (list instanceof ArrayList) { return "ArrayList"; } else if (list instanceof Stack) { return "Stack"; } else if (list instanceof Vector) { return "Vector"; } else { return "List"; } } // 向list的指定位置插入COUNT个元素，并统计时间 private static void insertByPosition(List list) { long startTime = System.currentTimeMillis(); // 向list的位置0插入COUNT个数 for (int i=0; i 得到的结果如下
Stack : insert 100000 elements into the 1st position use time：834 msVector : insert 100000 elements into the 1st position use time：818 msLinkedList : insert 100000 elements into the 1st position use time：10 msArrayList : insert 100000 elements into the 1st position use time：822 msStack : read 100000 elements by position use time：5 msVector : read 100000 elements by position use time：3 msLinkedList : read 100000 elements by position use time：6088 msArrayList : read 100000 elements by position use time：2 msStack : delete 100000 elements from the 1st position use time：857 msVector : delete 100000 elements from the 1st position use time：835 msLinkedList : delete 100000 elements from the 1st position use time：6 msArrayList : delete 100000 elements from the 1st position use time：849 ms
根据结果，可以很明显的看出ArrayList、LinkedList、Vector、Stack的性能有很大的区别。
| 操作 | ArrayList | LinkedList | Vector | Stack |
|---|---|---|---|---|
| 读取 | 2ms | 6088ms | 3ms | 5ms |
| 插入 | 822ms | 10ms | 818ms | 834ms |
| 删除 | 849ms | 6ms | 835ms | 857ms |
读取：ArrayList > Vector > Stack > LinkedList
插入：LinkedList > Vector > ArrayList > Stack 删除：LinkedList > Vector > ArrayList > Stack三、插入的分析
LinkedList
// 在index前添加节点，且节点的值为elementpublic void add(int index, E element) { addBefore(element, (index==size ? header : entry(index)));}// 获取双向链表中指定位置的节点private Entry entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry e = header; // 获取index处的节点。 // 若index < 双向链表长度的1/2,则从前向后查找; // 否则，从后向前查找。 if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e;}// 将节点(节点数据是e)添加到entry节点之前。private Entry addBefore(E e, Entry entry) { // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e Entry newEntry = new Entry (e, entry, entry.previous); // 插入newEntry到链表中 newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry;} 从中，我们可以看出：通过add(int index, E element)向LinkedList插入元素时。先是在双向链表中找到要插入节点的位置index；找到之后，再插入一个新节点。
双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。ArrayList
// 将e添加到ArrayList的指定位置public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++;} 在这里面有一个非常耗时的操作
System.arraycopy(elementData, index, elementData, index + 1, size - index);
Vector
public synchronized void insertElementAt(E obj, int index) { modCount++; if (index > elementCount) { throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } ensureCapacityHelper(elementCount + 1); System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); elementData[index] = obj; elementCount++; } public void add(int index, E element) { insertElementAt(element, index); } 可以看到Vector和ArrayList是一样的，都调用了System.arraycopy。由于Stack和继承与Vector，就不仔细分析了。
四、查找的分析
LinkedList
LinkedList随机访问的代码// 返回LinkedList指定位置的元素public E get(int index) { return entry(index).element;}// 获取双向链表中指定位置的节点private Entry entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry e = header; // 获取index处的节点。 // 若index < 双向链表长度的1/2,则从前先后查找; // 否则，从后向前查找。 if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e;} 从中，我们可以看出：通过get(int index)获取LinkedList第index个元素时。先是在双向链表中找到要index位置的元素；找到之后再返回。
双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。ArrayList
// 获取index位置的元素值public E get(int index) { RangeCheck(index); return (E) elementData[index];}private void RangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size);} 我们可以看到ArrayList直接返回数组中index位置的元素，而不需要像LinkedList一样进行查找。
通过源码发现Vector和Stack的操作方式和ArrayList一样，这里就不详细分析了。五、删除的分析
LinkedList
private E remove(Entrye) { if (e == header) throw new NoSuchElementException(); E result = e.element; e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; modCount++; return result;}
由于删除了某一节点因此调整相应节点的前后指针信息，如下：
e.previous.next = e.next;//预删除节点的前一节点的后指针指向预删除节点的后一个节点。 e.next.previous = e.previous;//预删除节点的后一节点的前指针指向预删除节点的前一个节点。
清空预删除节点：
e.next = e.previous = null;e.element = null;
交给gc完成资源回收，删除操作结束。
与ArrayList比较而言，LinkedList的删除动作不需要“移动”很多数据，从而效率更高。
ArrayList
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; } 恩，又是调用了System.arraycopy。
六、结论
| 操作 | ArrayList | LinkedList | Vector | Stack |
|---|---|---|---|---|
| 读取 | O(1) | O(n) | O(1) | O(1) |
| 插入 | O(n) | O(1) | O(n) | O(n) |
| 删除 | O(n) | O(1) | O(n) | O(n) |
- ArrayList(实现动态数组)，查询快（随意访问或顺序访问），增删慢。整体清空快，线程不同步(非线程安全)。数组长度是可变的百分之五十延长
- LinkedList（实现链表），查询慢，增删快。
- Vector（实现动态数组），都慢，被ArrayList替代。长度任意延长。线程安全（同步的类，函数都是synchronized）
- Stack（实现堆栈）继承于Vector，先进后出。
所以，快速访问ArrayList，快速增删LinkedList，单线程都可以用，多线程只能用同步类Vector