ArrayList与LinkedList
简介：
ArrayList和LinkedList就是分别对顺序表和双向链表的一种实现
顺序表：需要申请连续的内存空间保存元素，可以通过内存中的物理位置直接找到元素的逻辑位置。在顺序表中间插入or删除元素需要把该元素之后的所有元素向前or向后移动。
双向链表：不需要申请连续的内存空间保存元素，需要通过元素的头尾指针找到前继与后继元素（查找元素的时候需要从头or尾开始遍历整个链表，直到找到目标元素）。在双向链表中插入or删除元素不需要移动元素，只需要改变相关元素的头尾指针即可。
ArrayList与LinkedList的比较
1、ArrayList是实现了基于动态数组的数据结构,因为地址连续，一旦数据存储好了，查询操作效率会比较高（在内存里是连着放的）。
2、因为地址连续， ArrayList要移动数据,所以插入和删除操作效率比较低。
3、LinkedList基于链表的数据结构,地址是任意的，所以在开辟内存空间的时候不需要等一个连续的地址，对于新增和删除操作add和remove，LinedList比较占优势。
4、因为LinkedList要移动指针,所以查询操作性能比较低。
ArrayList与Vector的比较
1、Vector的方法都是同步的，是线程安全的，而ArrayList的方法不是，由于线程的同步必然要影响性能。因此，ArrayList的性能比Vector好。
2、当Vector或ArrayList中的元素超过它的初始大小时，Vector会将它的容量翻倍，而ArrayList只增加50%的大小，这样。ArrayList就有利于节约内存空间。
3、大多数情况不使用Vector，因为性能不好，但是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性。
4、Vector可以设置增长因子，而ArrayList不可以。
测试程序
import java.util.*;
public class Main {
public static void main(String[] args) {
long startTime,endTime;
ArrayList<Integer> arrayList = new ArrayList<>(300000);
LinkedList<Integer> linkedList = new LinkedList<>();
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=0;i<100000;i++){
arrayList.add(i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在ArrayList尾部插入100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=0;i<100000;i++){
linkedList.add(i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在LinkedList尾部插入100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=0;i<100000;i++){
arrayList.add(0,i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在ArrayList头部插入100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=0;i<100000;i++){
linkedList.add(0,i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在LinkedList头部插入100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=0;i<100000;i++){
arrayList.add(100000,i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在ArrayList中间插入100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=0;i<100000;i++){
linkedList.add(100000,i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在LinkedList中间插入100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=0;i<100000;i++){
arrayList.get(i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在ArrayList头部读取100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=0;i<100000;i++){
linkedList.get(i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在LinkedList头部读取100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=100000;i<200000;i++){
arrayList.get(i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在ArrayList中间读取100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=100000;i<200000;i++){
linkedList.get(i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在LinkedList中间读取100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=200000;i<300000;i++){
arrayList.get(i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在ArrayList尾部读取100000个元素： "+(endTime-startTime)+"ms");
startTime=System.currentTimeMillis(); //获取开始时间
for(int i=200000;i<300000;i++){
linkedList.get(i);
}
endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("在LinkedList尾部读取100000个元素： "+(endTime-startTime)+"ms");
return;
}
}
ArrayList尾部插入
public boolean add(E e) {
// 检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 直接在尾部添加元素
elementData[size++] = e;
return true;
}
对ArrayList的尾部插入，直接插入即可，无须额外的操作。
LinkedList尾部插入
add(E e)方法，该方法中调用了linkLast(E e)方法
public boolean add(E e) {
linkLast(e);
return true;
}
linkLast(E e)方法，可以看出，在尾部插入的时候，并不需要从头开始遍历整个链表，
因为已经事先保存了尾结点，所以可以直接在尾结点后面插入元素
void linkLast(E e) {
// 先把原来的尾结点保存下来
final Node<E> l = last;
// 创建一个新的结点，其头结点指向last
final Node<E> newNode = new Node<>(l, e, null);
// 尾结点置为newNode
last = newNode;
if (l == null)
first = newNode;
else
// 修改原先的尾结点的尾结点，使其指向新的尾结点
l.next = newNode;
size++;
modCount++;
}
总结
对于尾部插入而言，ArrayList与LinkedList的性能几乎是一致的
ArrayList头部插入
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 把原来数组中的index位置开始的元素全部复制到index+1开始的位置（其实就是index后面的元素向后移动一位）
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 插入元素
elementData[index] = element;
size++;
}
add(int index, E element)方法，可以看到通过调用系统的数组复制方法来实现了元素的移动。所以，插入的位置越靠前，需要移动的元素就会越多
LinkedList头部插入
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
add(int index, E element)方法，该方法先判断是否是在尾部插入，如果是调用linkLast()方法，否则调用linkBefore()，那么是否真的就是需要重头开始遍历呢？我们一起来看看
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
在头尾以外的位置插入元素当然得找出这个位置在哪里，这里面的node()方法就是关键所在，这个函数的作用就是根据索引查找元素，但是它会先判断index的位置，如果index比size的一半(size >> 1,右移运算，相当于除以2)要小，就从头开始遍历。
否则，从尾部开始遍历。从而可以知道，对于LinkedList来说，操作的元素的位置越往中间靠拢，效率就越低
总结
对于LinkedList来说，头部插入和尾部插入时间复杂度都是O(1)
但是对于ArrayList来说，头部的每一次插入都需要移动size-1个元素，效率可想而知
但是如果都是在最中间的位置插入的话，ArrayList速度比LinkedList的速度快将近100倍
ArrayList、LinkedList查找
对于ArrayList，无论什么位置，都是直接通过索引定位到元素，时间复杂度O(1)
而对于LinkedList查找，其核心方法就是上面所说的node()方法，所以头尾查找速度极快，越往中间靠拢效率越低
