目录
ArrayList 特点和底层实现
ArrayList 底层是用数组实现的存储。 特点：查询效率高，增删效率低，线程不安全。 在 List 的多个实现类中，我们一般使用它来处理业务。查看源码：
我们可以看出 ArrayList 底层使用 Object 数组来存储元素数据。所有的方法，都围绕这个核心的 Object 数组来开展。
我们知道，数组长度是有限的，而 ArrayList 是可以存放任意数量的对象，长度不受限 制，那么它是怎么实现的呢？本质上就是通过定义新的更大的数组，将旧数组中的内容拷贝 到新数组，来实现扩容。 ArrayList 的 Object 数组初始化长度为 10，如果我们存储满了这个 数组，需要存储第 11 个对象，就会定义新的长度更大的数组，并将原数组内容和新的元素 一起加入到新数组中，源码如下：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 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:
elementData = Arrays.copyOf(elementData, newCapacity);
}LinkedList 特点和底层实现
LinkedList 底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。
双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前 一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到 所有节点。
每个节点都应该有 3 部分内容：
class Node {
Node prev; //前一个节点
Object item; //本节点保存的数据
Node next; //后一个节点
}查看 LinkedList 的源码，可以看到里面包含了双向链表的相关代码：
Vector 向量
Vector 底层是用数组实现的 List，相关的方法都加了同步检查，因此“线程安全,效率低”。 比如，indexOf 方法就增加了 synchronized 同步标记。
如何选用 ArrayList、LinkedList、Vector?
需要线程安全时，用 Vector。
不存在线程安全问题时，并且查找较多用 ArrayList（一般使用它）。
不存在线程安全问题时，增加或删除元素较多用 LinkedList。
