Java list的实现类

本文是根据博文整理

Java中，List接口一共有三个实现类：ArrayList、Vector和LinkedList。

其中ArrayList和Vector都是利用数组这一个数据结构实现的，所以具有较强的随机访问能力，但是相应的，插入和删除的能力就比较弱：ArrayList和Vector要求实现所用的数组的元素之间是不能有间隔的，换言之就是如果你在中间删除了一个元素，后面的都必须向前移动来补位。我猜这是为了防止数组碎片化的问题，而在末尾插入和删除的代价相对比较小。还有一个问题，就是数组在初始化的时候要约定一个大小，所以当插入的元素个数大于当前空间的最大大小时，就需要申请新的内存空间、创建新的数组并将现有数据拷贝过去（ArrayList在内存不够时默认是扩展50% + 1个，Vector是默认扩展1倍），这也是很耗时间的。所以这两种适合随机访问和遍历，不适合大量的增删。

Vector和ArrayList的区别在于Vector支持线程之间的同步，也就是只有一个线程可以在同一时刻写入该Vector。但是做到这种功能需要花费很高的代价，使用起来比较慢。

LinkedList是利用链表实现的，那么相应的，它的增删代价比较小，但是随机访问的能力就弱了。ListedList还定义了比List接口要求的更多的方法，例如操作表头和表尾的元素，可以用来当成队列、堆栈或者双向列表使用。

究竟使用哪一种实现类要看具体的使用场景。如果不涉及到多线程的话Vector不用也没事，ArrayList时候随机访问比较多的情况，LinkedList适合增删比较多的情况。