JAVA集合之List ＞＞ Arraylist/LinkedList/Vector结构

在Java开发过程中，可能经常会使用到List作为集合来使用，List是一个接口承于Collection的接口，表示着有序的列表。而我们要讨论的是它下面的实现类Arraylist/LinkedList/Vector的数据结构及区别。

ArrayList

ArrayList：底层为数组结构，而数组的查询速度都是O(1)很快的，增删稍慢（新增对象，如果超过数组设置的大小，需要扩容。删除对象，则需要对数组重排序）。

参考源码：

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; ......此处省略其他参数代码/*** 构造具有指定初始容量的空列表.** @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构造函数，证明它是一个数组结构。对于add的扩容，及remove的重排序由于代码比较多就没有贴，大家可以直接去看源码（add 扩容方法：grow(int minCapacity)、remove重排序：System.arraycopy）

LinkedList

LinkedList：底层为链表结构，增删查等操作，如果是指定位置，则速度稍慢（需要遍历链表，直到指定位置），如果不是指定位置则速度快（默认操作链头、链尾）。

对于指定位置的操作，都会调用源码中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. 默认从尾部新增元素*/void linkLast(E e) {//获取尾部元素final Node<E> l = last;//将尾部元素作为上一个元素，并创建一个新的当前元素final Node<E> newNode = new Node<>(l, e, null);//将新元素更新为最后一个元素last = newNode;if (l == null)    // 如果为空，则将新元素赋值到第一个元素(first)first = newNode;else              //否则将新增前的最后一个元素的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对于无参数新增，只需要往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)            // 如果指定位置是最后一个，则从尾部插入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. 默认从尾部新增元素*/void linkLast(E e) {//获取尾部元素final Node<E> l = last;//将尾部元素作为上一个元素，并创建一个新的当前元素final Node<E> newNode = new Node<>(l, e, null);//将新元素更新为最后一个元素last = newNode;if (l == null)    // 如果为空，则将新元素赋值到第一个元素(first)first = newNode;else              //否则将新增前的最后一个元素的next存放新元素l.next = newNode;size++;modCount++;}/*** 返回指定位置的元素*/Node<E> node(int index) {//如果小于链表的大小，则从第一个元素开始循环获取到指定位置的元素 if (index < (size >> 1)) {Node<E> x = first;                 //链表的第一个元素开始for (int i = 0; i < index; i++)    //循环链表，直到指定位置x = x.next;                   return x;                         } else {                               //否则获取最后一个元素返回Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}/*** 在指定位置的元素前插入新元素*/void linkBefore(E e, Node<E> succ) {// 指定位置的前一个元素final Node<E> pred = succ.prev; // 创建新元素   final Node<E> newNode = new Node<>(pred, e, succ);// 将新元素作为指定位置元素的前一个元素succ.prev = newNode;// 指定位置的前一个元素如果为空，则将新元素放入到first if (pred == null)first = newNode;else// 指定位置前一个元素的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对于指定位置新增，需要调用node(int index)方法，用于遍历获取指定位置的元素。对于性能来说是有影响的。

remove、get方法也一样，只要是指定位置的操作，都会调用node(int index)方法对链表进行遍历获取

Vector

Vector：底层为数组结构，与ArrayList差不多，但是线程同步的，因为效率低，基本被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所以只能单线程执行。