在Java開發(fā)過程中，可能經(jīng)常會使用到List作為集合來使用，List是一個(gè)接口承于Collection的接口，表示著有序的列表。而我們要討論的是它下面的實(shí)現(xiàn)類Arraylist/LinkedList/Vector的數(shù)據(jù)結(jié)構(gòu)及區(qū)別。

ArrayList

ArrayList：底層為數(shù)組結(jié)構(gòu)，而數(shù)組的查詢速度都是O(1)很快的，增刪稍慢（新增對象，如果超過數(shù)組設(shè)置的大小，需要擴(kuò)容。刪除對象，則需要對數(shù)組重排序）。

參考源碼：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{/*** Default initial capacity.*/private static final int DEFAULT_CAPACITY = 10;/*** Shared empty array instance used for empty instances.*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** Shared empty array instance used for default sized empty instances. */private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData; ......此處省略其他參數(shù)代碼/*** 構(gòu)造具有指定初始容量的空列表.** @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 an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @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;}}.....省略其他代碼
}

以上源碼只貼了Arraylist構(gòu)造函數(shù)，證明它是一個(gè)數(shù)組結(jié)構(gòu)。對于add的擴(kuò)容，及remove的重排序由于代碼比較多就沒有貼，大家可以直接去看源碼（add 擴(kuò)容方法：grow(int minCapacity)、remove重排序：System.arraycopy）

LinkedList

LinkedList：底層為鏈表結(jié)構(gòu)，增刪查等操作，如果是指定位置，則速度稍慢（需要遍歷鏈表，直到指定位置），如果不是指定位置則速度快（默認(rèn)操作鏈頭、鏈尾）。

對于指定位置的操作，都會調(diào)用源碼中node(int index)方法，該方法就是遍歷鏈表，直到指定位置返回元素

無參add 源碼參考：

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{transient int size = 0;transient Node<E> first;transient Node<E> last;......省略N多代碼public boolean add(E e) {linkLast(e);return true;}/*** Links e as last element. 默認(rèn)從尾部新增元素*/void linkLast(E e) {//獲取尾部元素final Node<E> l = last;//將尾部元素作為上一個(gè)元素，并創(chuàng)建一個(gè)新的當(dāng)前元素final Node<E> newNode = new Node<>(l, e, null);//將新元素更新為最后一個(gè)元素last = newNode;if (l == null)    // 如果為空，則將新元素賦值到第一個(gè)元素(first)first = newNode;else              //否則將新增前的最后一個(gè)元素的next存放新元素l.next = newNode;size++;modCount++;}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;}}}

LinkedList對于無參數(shù)新增，只需要往Last元素的Next放入新增的元素，然后更新全局Last位置即可，所以沒有速度的影響。對于addFirst、addLast等代碼沒貼，可自行了解，都差不多。

有參add 源碼參考：

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{    public void add(int index, E element) {checkPositionIndex(index);    // 檢查位置是否存在if (index == size)            // 如果指定位置是最后一個(gè)，則從尾部插入linkLast(element);else// node(index) 會遍歷鏈表到指定位置，返回指定位置的元素// linkBeforelinkBefore(element, node(index));}// 檢查位置是否存在private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}/*** Links e as last element. 默認(rèn)從尾部新增元素*/void linkLast(E e) {//獲取尾部元素final Node<E> l = last;//將尾部元素作為上一個(gè)元素，并創(chuàng)建一個(gè)新的當(dāng)前元素final Node<E> newNode = new Node<>(l, e, null);//將新元素更新為最后一個(gè)元素last = newNode;if (l == null)    // 如果為空，則將新元素賦值到第一個(gè)元素(first)first = newNode;else              //否則將新增前的最后一個(gè)元素的next存放新元素l.next = newNode;size++;modCount++;}/*** 返回指定位置的元素*/Node<E> node(int index) {//如果小于鏈表的大小，則從第一個(gè)元素開始循環(huán)獲取到指定位置的元素 if (index < (size >> 1)) {Node<E> x = first;                 //鏈表的第一個(gè)元素開始for (int i = 0; i < index; i++)    //循環(huán)鏈表，直到指定位置x = x.next;                   return x;                         } else {                               //否則獲取最后一個(gè)元素返回Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}/*** 在指定位置的元素前插入新元素*/void linkBefore(E e, Node<E> succ) {// 指定位置的前一個(gè)元素final Node<E> pred = succ.prev; // 創(chuàng)建新元素   final Node<E> newNode = new Node<>(pred, e, succ);// 將新元素作為指定位置元素的前一個(gè)元素succ.prev = newNode;// 指定位置的前一個(gè)元素如果為空，則將新元素放入到first if (pred == null)first = newNode;else// 指定位置前一個(gè)元素的next 放入新元素pred.next = newNode;size++;modCount++;}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;}}
}

LinkedList對于指定位置新增，需要調(diào)用node(int index)方法，用于遍歷獲取指定位置的元素。對于性能來說是有影響的。

remove、get方法也一樣，只要是指定位置的操作，都會調(diào)用node(int index)方法對鏈表進(jìn)行遍歷獲取

Vector

Vector：底層為數(shù)組結(jié)構(gòu)，與ArrayList差不多，但是線程同步的，因?yàn)樾实?#xff0c;基本被ArrayList替代了

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}public synchronized E remove(int index) {modCount++;if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);E oldValue = elementData(index);int numMoved = elementCount - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--elementCount] = null; // Let gc do its workreturn oldValue;}public synchronized E get(int index) {if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);return elementData(index);}}

源碼上可以看到add、get、remove等都加上了synchronized所以只能單線程執(zhí)行。