ArrayList

底层使用数组实现，适合插入较少

适合随机查找O(1)，原理：地址连续

扩容O(n) 源码中int newCapacity = oldCapacity + (oldCapacity » 1);即扩容为原来的1.5倍

插入O(n)，尾插为O(1)，最坏O(n)，平均即为 O(n)

LinkedList

底层使用(双向)链表，适合插入较多

随机查找O(n)

头尾插入O(1)

使用场景

ArrayList：一般场景，都是用ArrayList来代表一个集合，只要别频繁的往里面插入和灌入大量的元素就可以了，遍历，或者随机查，都可以。

LinkedList：适合，频繁的在list中插入和删除某个元素，然后尤其是LinkedList他其实是可以当做队列来用的，这个东西的话呢，我们后面看源码的时候，可以来看一下，先进先出，在list尾部怼进去一个元素，从头部拿出来一个元素。如果要在内存里实现一个基本的队列的话，可以用LinkedList