一，线程安全性
Vector、Stack：线程安全
ArrayList、LinkedList：非线程安全
二，实现方式
LinkedList：双向链表
ArrayList，Vector，Stack：数组
三，容量扩展方面
由于ArrayList和Vector（Stack继承自Vector，只在Vector的基础上添加了几个Stack相关的方法，故之后不再对Stack做特别的说明）使用数组实现，当数组长度不够时，其内部会创建一个更大的数组，然后将原数组中的数据拷贝至新数组中
//ArrayList public boolean add(E e) { ensureCapacity(size + 1); elementData[size++] = e; return true; } public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; //如果这次扩展不能满足要求，那就直接用minCapacity if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } } 如需扩展，则每次至少扩展至(原长度*3)/2 + 1
//Vector public synchronized void addElement(E obj) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = obj; } private void ensureCapacityHelper(int minCapacity) { int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object[] oldData = elementData; int newCapacity = (capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2); //如果这次扩展不能满足要求，那就直接用minCapacity if (newCapacity < minCapacity) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); } } 如果在创建Vector时不指定capacityIncrement（自动扩展长度）的值，如需扩展，则每次至少扩展至原长度的2倍
四，效率方面
这里仅仅比较ArrayList和LinkedList之间的效率差异
1，查询
ArrayList直接通过下标进行定位
//ArrayList public E get(int index) { RangeCheck(index);//检查下标是否超过数组长度 return (E) elementData[index]; } LinkedList则需要进行遍历，平均遍历次数应为n/4
//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; //size >>1 相当于size/2 //由于LinkedList由双向链表实现，故从离得较近的一端开始遍历更快 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; } 对于指定位置查询，由于可以通过下标直接进行定位，ArrayList的速度远快于LinkedList
但是如果都为首尾位置的查询，情况会大为不同，因为LinkedList也是可以直接定位到首尾位置的
//LinkedList public E getFirst() { if (size==0) throw new NoSuchElementException(); return header.next.element; } public E getLast() { if (size==0) throw new NoSuchElementException(); return header.previous.element; } 此时ArrayList和LinkedList的效率相同
2，插入
对于ArrayList，指定位置插入有可能首先需要对数组容量进行扩展，之后还有可能导致数组中的数据需要顺次移动（代码中通过数组拷贝实现，避免了数据一个一个的移动），极端情况下插入一个数据将进行两次数组拷贝
//ArrayList public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+1); //如必要，将对数组容量进行扩展 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } 如果不指定插入位置，则插入至数组末端，此时只需考虑可能的数组容量扩展对性能带来的影响
//ArrayList public boolean add(E e) { ensureCapacity(size + 1); elementData[size++] = e; return true; } 由于LinkedList是由链表实现的，并没有指定位置插入的方法，即便如此，一切也显得如此美好
/LinkedList public boolean add(E e) { addBefore(e, header); return true; } private Entry addBefore(E e, Entry entry) { Entry newEntry = new Entry (e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; } 当然了，LinkedList可以直接将数据插入至首尾
//LinkedList public void addFirst(E e) { addBefore(e, header.next); } public void addLast(E e) { addBefore(e, header); } 总体来说，LinkedList效率高于ArrayList，即使在末尾插入，ArrayList也需要考虑可能的容量扩展对性能带来的影响
3，修改
和查询属于同一种情况
4，删除
指定位置的删除和插入属于同一种情况
除了删除指定位置数据，ArrayList和LinkedList都包含一个clear()方法用来清除所有数据
//ArrayList public void clear() { modCount++; // Let gc do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } [java] view plain copy 在CODE上查看代码片派生到我的代码片//LinkedList public void clear() { Entry e = header.next; while (e != header) { Entry next = e.next; e.next = e.previous = null; e.element = null; e = next; } header.next = header.previous = header; size = 0; modCount++; } 由于都需要进行遍历，故效率相同