Java核心数据结构总结
JDK提供了一组主要的数据结构的实现，如List、Set、Map等常用结构，这些结构都继承自java.util.collection接口。
List接口
List有三种不同的实现，ArrayList和Vector使用数组实现，其封装了对内部数组的操作。LinkedList使用了循环双向链表的数据结构，LinkedList链表是由一系列的链表项连接而成，一个链表项包括三部分：链表内容、前驱表项和后驱表项。
LinkedList的表项结构如图：
LinkedList表项间的连接关系如图：
可以看出，无论LinkedList是否为空，链表都有一个header表项，它即表示链表的开头也表示链表的结尾。表项header的后驱表项便是链表的第一个元素，其前驱表项就是链表的最后一个元素。
对基于链表和基于数组的两种List的不同实现做一些比较：
1、增加元素到列表的末尾：
在ArrayList中源代码如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add()方法性能的好坏取决于grow()方法的性能：
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);
}
可以看出，当ArrayList对容量的需求超过当前数组的大小是，会进行数组扩容，扩容的过程中需要大量的数组复制，数组复制调用System.arraycopy（）方法，操作效率是非常快的。
在LinkedList源码中add()方法：
public boolean add(E e) {
linkLast(e);
return true;
}
linkLast（）方法如下：
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++;
}
LinkedList是基于链表实现，因此不需要维护容量大小，但是每次都新增元素都要新建一个Node对象，并进行一系列赋值，在频繁系统调用中，对系统性能有一定影响。性能测试得出，在列表末尾增加元素，ArrayList比LinkedList性能要好，因为数组是连续的，在末尾增加元素，只有在空间不足时才会进行数组扩容，大部分情况下追加操作效率还是比较高的。