关于Java中集合的List集合

关于Java中List集合的细节问题

Java中有几种常用的数据结构，其中主要继承Collection和Map两个主要接口（只提供方法，不提供实现类），而程序中最终使用的数据结构是这些接口的实现类。

Collection接口

1. 定义的是所有单列集合中的共性方法
2. 所有单列集合都可以使用的共性方法
3. 没有带索引的方法

List接口

Java的List是非常常用的数据类型。List是有序的Collection，一共有三个实现类分别为ArrayList、LinkedList、Vector。

List接口实现类*有的特性

1. 有序的集合（存储和取出元素顺序相同）
2. 允许重复元素
3. 带索引，可以遍历

ArrayList

ArrayList是最常用的List实现类，内部是通过数组实现的。数组是在内存中开辟一段连续的空间，并在此空间中存放元素。
特点

1. 查询快，数组的地址是连续的，我们查找数组中的元素时是通过查找数组的首地址值找到数组，再通过索引值找到对应的元素。
2. 增删慢，数组的长度是固定的，我们要增删一个元素，必须创建一个新的数组，把源数组复制过来（源数组被垃圾回收）

使用默认构造方法如

List arrayList = new ArrayList();

初始容量被设置为10。当ArrayList中的元素超过10个以后，会重新分配内存空间，使数组的大小增长到16。容量变化的公式为：旧内存空间*1.5 + 1 = 新内存空间，若给定了初始容量也是相同的公式。
ArrayList在增加元素时首先会进行判断容量是否适当，不适当时就会将创建一个新的增加容量的数组，然后将原数组拷贝过去，将原数组重新赋值指向新数组，删除元素时会将删除元素以后元素的index前移一位，然后将空出来的位置置null，由junk销毁。

LinkedList

由一系列结点（链表中每一个元素称为一个结点）组成，结点可以在运行时动态生成，每个结点包括两部分，一部分是存储数据的数据域，另一部分是存储下一个结点地址的指针域。LinkedList的底层实现是一个双向链表
特点

1. 查询慢，每次查询元素时，通过连接的节点依次向后查找
2. 增删快，只需修改连接下个元素的地址即可

LinkedList是双向链表，没有初始化大小，也没有扩容机制，只需在头尾一直增加即可

Vector

Vector和ArrayList一样，也是通过数组实现的，不过不同的是Vector是线程安全的（所有操作元素的方法都被sychronized修饰），即某一时刻只能有一个线程能够写Vector，但实现同步需要很大的花费，因此它比ArrayList慢。
Vector也不是绝对线程安全的，比如在使用下列代码时，当if对vector进行判断时，判断完毕后，这时vector.contains方法的锁已经释放，在执行add方法之前有短暂的空隙有可能会被其他线程获取锁，然后改变vector的状态，因此对于复合操作，Vector仍然需要同步处理。

if (!vector.contains(element)) 
    vector.add(element); 
    ...
}

Vector的初始容量为10，当元素个数超过当前容量时进行扩容，扩容因子为1，即
扩容后容量=当前容量*2