Java集合--List及其实现类
List集合存放的元素是有序，可重复的。
文档定义如下：
public interface List<E> extends Collection<E> {}
List继承了Collection<E>接口，由于集合中存放的都是对象，因此List对象在add操作的时候可以add(null)。
这里主要介绍List的三个实现类ArrayList、LinkedList、Vector。
先给出它们三个的定义：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
从它们各自的定义我们能发现ArrayList和Vector都实现了List<E>接口，这也是我们平时总是定义列表的时候习惯写List<E> list = new ArrayList<>();同时，我们还发现二者都实现了RandomAccess接口，而LinkedList没有实现RandomAccess接口，RandomAccess接口的目的就是告诉我们，实现了该接口的类支持高速随机访问。（当查阅RandomAccess定义的时候，我们发现RandomAccess只是定义了一下，内部并没有任何的方法，我猜这里可能就是为了标识一下吧，标识 -- 实现了该接口的类都支持高速随机访问[当然最可靠的办法还是看源码]）
从另一角度还可以分析ArrayList和Vector支持高速随机访问，而LinkedList不支持。ArrayList和Vector底层是通过数组实现，LinkedList底层是通过双向链表实现。我们知道数组的优点是读取方便，即可以通过索引直接读取值，而链表的读取需要从前向后依次查找，但是链表的删除和插入方便。因此这里最能解释为什么ArrayList和Vector支持高速随机访问，而LinkedList不支持。
ArrayList和Vector的区别是什么呢？
ArrayList中方法都没有做同步，因此ArrayList是线程不安全的；Vector中方法基本都做了同步，因此是线程安全的。我们知道同步是高损耗的，平时尽可能的不去使用同步，除非业务需要，比如转账操作。这也能解释我们平时定义列表的时候为啥总是习惯写List<E> list = new ArrayList<>();首先没有同步机制，低耗；另一个平时大多数情况下都是读操作居多。
下面以列表的add方法为例，查看一下源码，拿ArrayList和LinkedList对比分析：（ArrayList和Vector在源码中区别就在于有没有关键字synChronized，这里就不分析了）
ArrayList中的add()方法
/**
* 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) {
//1、判断数组容量是否够用 2、赋值 3、return
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
继续看ensureCapacityInternal()的源码：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//主要是ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//这个modCount变量的作用是计数，记录修改次数（发现：变量modCount经常出现在线程不安全的方法中）
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
再继续看grow方法：
/**
* 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;
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:
//我们看到这里使用了数组的复制方法，进而实现列表的add方法
elementData = Arrays.copyOf(elementData, newCapacity);
}
LinkedList中的add方法
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
继续看linkLast方法：
/**
* 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 = newNode;
else
l.next = newNode;
size++;
modCount++;
}
继续看Node的定义：
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因为使用了双向链表，插入和删除都很方便。
转载于:https://www.jianshu.com/p/56f3567ef910