集合框架中ArrayList和LinkedList的区别与联系

                            集合框架
1，Collection<E>在java.util包中，Collection是 层次结构中的根接口。
   Collection 表示一组对象，这些对象也称为 collection 的元素。
   一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。
   JDK 不提供此接口的任何直接 实现：它提供更具体的子接口（如 Set 和 List，）实现；

2，列表 List,有序的 collection（也称为序列）; 列表通常允许重复的元素。
   常用的List实现类： LinkedList Stack Vector
(1)ArrayListList是实现了基于动态数组的数据结构，是有序的，可重复的，长度可变的，有下标的，地址连续的的数组序列；
而 LinkedList是实现了基于链表的数据结构，是有序的，可重复的，长度可变的，有下标的，地址任意的,各个数据之间通过引用关联的链式序列；而且一个节点就是一个对象，包含了自己前一个节点和后一个节点的地址；


（2）ArrayListList添加元素的时候，需要判断存放元素的数组是否需要扩容；在指定位置添加元素或者移除指定元素的时候，需要移动比较多的元素，所以做插入删除操作时效率较低，但是由于是地址连续的一旦数据存储完了，查询操作效率比较高；且对于多线程的操作，不是线程同步的；

（3） LinkedList是通过移动链表指针添加和删除元素的，效率较高；但是查询操作效率较低；
 
（4）空间复杂度分析：LinkedList中每个对象都对应于链表中的一个元素，且该对象不仅存储自身的信息，还要存储相邻节点的地址信息，因此，在LinkedList结构中将有一个很大的空间开销；而ArrayList使用内置数组来存储信息，且默认数组初始容量为10，当数组需要增长时，新的容量增长率为50%， 这意味着当有大量的ArrayListList对象时，由于ArrayListList本身的工作方式，最终将会有很大的空间被浪费掉，所以ArrayListList初始化的时候可以指定大小，如果你知道大小，在创建的时候最好指定；

     ArrayList(int initialCapacity) ， 构造一个具有指定初始容量的空列表。
     ArrayList() ， 构造一个初始容量为 10 的空列表。