一、List集合概括
List集合与Collection的继承关系：
1. List是一个接口，它继承与Collection接口，代表有序的队列。
2. AbstractList是一个抽象类，它继承与AbstractCollection。AbstractList实现了List接口中除了size()、get(int location)之外的方法。
3. AbstractSequentialList是一个抽象类，它继承与AbstrctList。AbstractSequentialList实现了“链表中，根据index索引值操作链表的全部方法”。
4. ArrayList、LinkedList、Vector和Stack是List的四个实现类。
5. Vector是基于数组实现的。是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。
6. Stack是基于数组实现的。继承了Vector相关特点，同时具有“先进后出”特性。
二、ArrayList和LinkedList的区别
- LinkedList是基于双向链表结构实现了。是个双向链列表，也可做堆栈、队列使用。
- ArrayList是基于数组结构实现的。是个数组队列，可动态扩容数组的容量。
- ArrayList在随机访问set和get比LinkedList的效率更高，因为在LinkedList要通过遍历查询移动指针，而ArrayList只需通过index在数组直接取出即可。
- 在网上看了很多资料，都说LinkedList在插入和删除（add和remove）元素上，效率比ArrayList更高，因为ArrayList在插入或删除要复制并移动数组。对于添加和删除，ArrayList和LinkedList在速度上并没有谁快谁慢，这是相对的。
下面重点比较分析LinkedList和ArrayList。
ArrayList中的随机访问、添加和删除部分源码如下
//获取index位置的元素值
public E get(int index) {
rangeCheck(index); //首先判断index的范围是否合法
return elementData(index);
}
//将index位置的值设为element，并返回原来的值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//将element添加到ArrayList的指定位置
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index以及index之后的数据复制到index+1的位置往后，即从index开始向后挪了一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element; //然后在index处插入element
size++;
}
//删除ArrayList指定位置的元素
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//向左挪一位，index位置原来的数据已经被覆盖了
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//多出来的最后一位删掉
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
LinkedList中的随机访问、添加和删除部分源码如下：
//获得第index个节点的值
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//设置第index元素的值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//在index个节点之前添加新的节点
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//删除第index个节点
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//定位index处的节点
Node<E> node(int index) {
// assert isElementIndex(index);
//index<size/2时，从头开始找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //index>=size/2时，从尾开始找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
程序测试：
public class ListTest {
private static final int COUNT=100000;//10万
static LinkedList<Integer> linkedList = new LinkedList<Integer>();
static ArrayList<Integer> arrayList=new ArrayList<Integer>();
public static void main(String[] args) {
System.out.println("------插入10万数据------");
insertData(linkedList);
insertData(arrayList);
System.out.println();
System.out.println("------读取10万数据------");
readData(linkedList);
readData(arrayList);
System.out.println();
System.out.println("------删除10万数据------");
removeData(linkedList);
removeData(arrayList);
}
/**
* 插入数据，计算插入10万条所需的时间
*/
@SuppressWarnings("unused")
public static void insertData(List<Integer> list) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
list.add(0,i);
}
long endTime = System.currentTimeMillis();
if (list instanceof LinkedList) {
System.out.println("LinkedList插入时间："+(endTime-startTime)+"ms");
}
if (list instanceof ArrayList) {
System.out.println("ArrayList插入时间："+(endTime-startTime)+"ms");
}
}
/**
* 读取数据，计算读取10万条所需的时间
*/
@SuppressWarnings("unused")
private static void readData(List<Integer> list) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
if (list instanceof LinkedList) {
System.out.println("LinkedList读取时间："+(endTime-startTime)+"ms");
}
if (list instanceof ArrayList) {
System.out.println("ArrayList读取时间："+(endTime-startTime)+"ms");
}
}
/**
* 删除数据，计算删除10万条所需的时间
*/
@SuppressWarnings("unused")
private static void removeData(List<Integer> list) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
list.remove(0);
}
long endTime = System.currentTimeMillis();
if (list instanceof LinkedList) {
System.out.println("LinkedList删除时间："+(endTime-startTime)+"ms");
}
if (list instanceof ArrayList) {
System.out.println("ArrayList删除时间："+(endTime-startTime)+"ms");
}
}
}
编译运行的结果：
------插入10万数据------ LinkedList插入时间：13ms ArrayList插入时间：737ms ------读取10万数据------ LinkedList读取时间：7312ms ArrayList读取时间：2ms ------删除10万数据------ LinkedList删除时间：7ms ArrayList删除时间：612ms
从上面的结果可以看出：
1. ArrayList在随机访问get元素的效率明显比LinkedList高出很多，因为ArrayList只要通过index就可以直接获取元素值，而LinkedList则不同，需要通过for遍历查找，当index<size/2时，此时从集合左边向右查询，反之从右向左查询，虽然在一定程度提高了查询的效果，但相对于ArrayList还是慢了很多很多。所以在使用LinkedList时，切记一定大量进行随机访问，如果数据超大的话，可能会导致线程阻塞。
2. 从上面的结果，第一直觉得出结论就是LinkedList在添加和删除操作会比ArrayList快，其实并不然，ArrayList在添加和删除的过程中，耗时主要是System.arraycopy(……)函数所引起的，它会改变数组的索引要重新排列；而LinkedList则要通过for遍历index的所处的节点再插入或删除数据，所有一定程度很难说谁快谁慢，影响LinkedList添加操作的效率，主要看插入的位置index，同样的也可以通过程序验证：
前面测试index是0，下面修改插入的index
/**
* 插入数据，计算插入10万条所需的时间
*/
@SuppressWarnings("unused")
public static void insertData(List<Integer> list) {
long startTime = System.currentTimeMillis();
/**
* 设置临界点temp,即在temp位置插入元素
* 给temp设置一个默认为50000，刚好一半，接下来手动改变测试
*/
int temp=50000;
for (int i = 0; i < COUNT; i++) {
if (i>=temp) {
list.add(temp,i);
}else {
list.add(0,i);
}
}
long endTime = System.currentTimeMillis();
if (list instanceof LinkedList) {
System.out.println("LinkedList插入时间："+(endTime-startTime)+"ms");
}
if (list instanceof ArrayList) {
System.out.println("ArrayList插入时间："+(endTime-startTime)+"ms");
}
}
编译结果：以中间值50000为临界点测试
temp=90000; ------插入10万数据------ LinkedList插入时间：139ms ArrayList插入时间：574ms temp=80000; ------插入10万数据------ LinkedList插入时间：497ms ArrayList插入时间：435ms temp=60000; ------插入10万数据------ LinkedList插入时间：1954ms ArrayList插入时间：329ms temp=50000; ------插入10万数据------ LinkedList插入时间：3027ms ArrayList插入时间：327ms temp=40000; ------插入10万数据------ LinkedList插入时间：4572ms ArrayList插入时间：320ms temp=10000; ------插入10万数据------ LinkedList插入时间：2260ms ArrayList插入时间：536ms temp=2000; ------插入10万数据------ LinkedList插入时间：478ms ArrayList插入时间：699ms
同样的LinkedList和ArrayList在最尾部逐个添加元素测试
if (list instanceof LinkedList) {
((LinkedList) list).addLast(i);
}else {
list.add(i);
}
编译结果：
------插入10万数据------ LinkedList插入时间：8ms ArrayList插入时间：6ms从上面的测试结果，很难完全定义LinkedList插入效率比ArrayList高，很大程度取决插入index位置。
由于LinkedList可以实现栈、队列以及双端队列等数据结构，所以当特定需要时候，使用LinkedList；当数据量大的时候，如果只需要在靠前的部分插入或删除数据，那也可以选用LinkedList。
如果有错误之处，请留言指正 ---谢谢！！！