【Java】Collection，List，ArrayList，

Collection

Collection是Java集合的一个根接口，JDK没有它的实现类。内部仅仅做add()，remove()，contains()，size()等方法的声明。

List

List接口是Collection接口的一个子类，在Collection基础上扩充了方法。同时可以对每个元素插入的位置进行精确的控制，它的主要实现类有Arraylist，Vector，LinkedList。
这里需要注意的是，List接口的实现类插入的值允许为空，也允许重复。

ArrayList

ArrayList实现了List接口，意味着可以插入空值，也可以插入重复的值，非同步，它是基于数组的一个实现。

• ArrayList可以插入空值，也可以插入重复值
• ArrayList是基于数组的时候，所有很多数组的特性也直接应用到了ArrayList。
• ArrayList的性能消耗主要来源于扩容和固定位置的增删。
• ArrayList创建的时候，需要考虑是否要初始化最小容量，以此避免扩容带来的消耗。

Vector

上述的ArrayList不是线程安全的。那么Vector就可以看作是ArrayList的一个线程安全版本。由于也是实现了List接口，所以也是可以插入空值，可以插入重复的值。它和HashTable一样，是属于一种同步容器，而不是一种并发容器。

• 可以插入空值，也可以插入重复值
• 也是基于数组的实现，所以很多数组的特性也直接应用到了Vector。
• 性能消耗也主要来源于扩容。
• 创建的时候需要考虑是否要初始化最小容量，以此避免扩容带来的消耗。
• 相当于ArrayList的线程安全版本，实现同步的方式是通过synchronized。

LinkedList

LinkedList实现了List接口，所以LinkedList也可以放入重复的值，也可以放入空值。LinkedList不支持同步。LinkedList不同于ArrrayList和Vector，它是使用链表的数据结构，不再是数组。
当进行增删的时候，只需要改变指针，并不会像数组那样出现整体数据的大规模移动，复制等消耗性能的操作。

对比

• 实现方法：
  • ArrayList，Vector是基于数组的实现
  • LinkedList是基于链表的实现
• 同步问题
  • Arraylist，LinkedList不是线程安全的
  • Vector是线程安全的，实现方式是在方法中加synchronized进行限定。
• 适用场景和性能消耗
  • ArrayList和Vector由于是基于数组的实现，所以在固定位置插入，固定位置删除这方面会直接是O(n)的时间复杂度，另外可能会出现扩容的问题，这是非常消耗性能的。
  • LinkedList不会出现扩容的问题，所以比较适合增删的操作。但是由于不是数组的实现，所以在定位方面必须使用遍历的方式，这会有O(n)的时间复杂度。