List包括ArrayList和LinkedList。他们的方法使用基本一样，但是底层的数据结构和实现却不一样。首先看下List和Collection 的关系

ArrayList和LinkedList两者的区别主要有3点：

     1 .ArrayList 是通过一个数组去保存数据的，LinkedList基于链表的数据结构实现

     2.如果是访问数据，比如get()，set()，ArrayList觉得优于LinkedList，LinkedList要移动指针，打破原有的链，但是ArrayList是根据下标来的

     3.ArrayList新增add()和删除操作remove()，LinedList比较占优势，ArrayList新增或者删除要移动原有的数据 

时间复杂度

查询操作：

     ArrayList的内部实现是基于对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端，访问列表中的某个指定元素没有更快的方法了。 

    假设我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来进行二分查找(binary search)，比较列表是ArrayList和LinkedList时的查询速度，看下面的程序： 

    

比较ArrayList 和LinkedList 二分查找的速度

    经过测试 ArrayList消耗大概15毫秒，LinkedList 则是2000多毫秒。

    基本上ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList。二分查找法使用的随机访问(random access)策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的

插入数据：

    ArrayList是使用数组实现的,若要从数组中删除或插入某一个对象，需要移动后段的数组元素，从而会重新调整索引顺序,调整索引顺序会消耗一定的时间，所以速度上就会比LinkedList要慢许多. 相反,LinkedList是使用链表实现的,若要从链表中删除或插入某一个对象,只需要改变前后对象的引用即可

    经过测试 ArrayList插入消耗的时间大概30毫秒，LinkedList 则是4毫秒。可以看出查询时LinkedList的速度更快。删除操作同理。

总结

1．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

2．LinkedList不支持高效的随机元素访问，因为是链式结构，所以查询时需要从头部开始依次查询

3．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了

ArrayList 是线性表（数组）

get() 直接读取第几个下标，复杂度 O(1)

add(E) 添加元素，直接在后面添加，复杂度O（1）

add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O（n）

remove（）删除元素，后面的元素需要逐个移动，复杂度O（n）

LinkedList 是链表的操作

get() 获取第几个元素，依次遍历，复杂度O(n)

add(E) 添加到末尾，复杂度O(1)

add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)

remove（）删除元素，直接指针指向操作，复杂度O(1)