Java 容器 & 泛型：二、ArrayList 、LinkedList和Vector比较

摘要: 原创出处 www.bysocket.com 泥瓦匠BYSocket 希望转载，保留摘要，谢谢！

继续上一篇的容器文章《认识容器》，泥瓦匠慢慢带你们走进 List 的容器解说。今天泥瓦匠想说说 ArrayList 、LinkedList 和 Vector 比较。

一、List 回顾

序列（List），有序的 Collection，正如它的名字一样，是一个有序的元素列表。确切的讲，列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2，并且如果列表本身允许 null 元素的话，通常它们允许多个 null 元素。实现 List 的有：ArrayList、LinkedList、Vector、Stack 等。值得一提的是，Vector 在 JDK1.1 的时候就有了，而List 在 JDK1.2 的时候出现，待会我们会聊到 ArrayList 和 Vector 的区别。

二、ArrayList vs. Vector

ArrayList 是一个可调整大小的数组实现的序列。随着元素增加，其大小会动态的增加。此类在 Iterator 或 ListIterator 迭代中，调用容器自身的 remove 和 add 方法进行修改，会抛出ConcurrentModificationException 并发修改异常。

注意，此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：

下面演示下相关 ArrayList 例子，ArrayList基本方法代码： 可以从控制台中得到以下结果：

在上面我们可以根据角标来增加(add)、删除(remove)、获取(get)列表里面元素。ArrayList 提供了 Iterator 迭代器来遍历序列。值得注意的是，迭代器的就相当于一个指针指向角标，next() 方法就相当于指针往后移一位。所以切记，用迭代器中一次循环用一次 next()。

下面演示下在 ConcurrentModificationException 的出现，及处理方案。用 Iterator 演示这个异常的出现：

运行，我们可以在控制台看到：

怎么解决的，先看清楚这个问题。问题描述很清楚，在创建迭代器之后，除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException。

因此我们应该这样修改代码，用 ListIterator 迭代器提供方法：

运行下，我们可以看到：

这样，我们成功解决了这个并发修改异常。把其中 List 元素删除，新增了一个 List02 的元素。

Vector 非常类似 ArrayList。早在 JDK1.1 的时候就出现了，以前没有所谓的 List 接口，现在此类被改进为实现 List 接口。但与新的 Collection 不同的是，Vector 是同步的。泥瓦匠想说的是 Vector，在像查询的性能上会比 ArrayList 开销大。下面演示下 Vector 的基本例子：

从方法上看几乎没差别，同样注意的是：此接口的功能与 Iterator 接口的功能是重复的。此外，Iterator 接口添加了一个可选的移除操作，并使用较短的方法名。新的实现应该优先考虑使用 Iterator 接口而不是 Enumeration 接口。

三、LinkedList 与 ArrayList 性能比

LinkedList 与 ArrayList 一样实现 List 接口，LinkedList 是 List 接口链表的实现。基于链表实现的方式使得 LinkedList 在插入和删除时更优于 ArrayList，而随机访问则比 ArrayList 逊色些。LinkedList 实现所有可选的列表操作，并允许所有的元素包括 null。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

LinkedList 和ArrayList 的方法时间复杂度总结如下图所示。

表中，add() 指添加元素的方法，remove() 是指除去（int index）角标。ArrayList 具有 O（N）的任意指数时间复杂度的添加/删除，但 O（1） 的操作列表的末尾。链表的 O（n） 的任意指数时间复杂度的添加/删除，但 O（1） 操作端/列表的开始。

泥瓦匠用代码验证下这个结论：

控制台输出如下：

对比下的话，其性能差距很明显。LinkedList在添加和删除中性能快，但在获取中性能差。从复杂度和测试结果，我们应该懂得平时在添加或者删除操作频繁的地方，选择LinkedList时考虑：

1、没有大量的元素的随机访问

2、添加/删除操作

下面用 LinkedList 实现一个数据结构–栈。泥瓦匠留给大家 LinkedList 的一些方法自己消化：

四、总结

泥瓦匠总结如下：

Vector 和 ArrayList

1、vector是线程同步的，所以它也是线程安全的，而arraylist是线程异步的，是不安全的。

2、记住并发修改异常 java.util.ConcurrentModificationException ，优先考虑ArrayList，除非你在使用多线程所需。

Aarraylist 和 Linkedlist

1、对于随机访问get和set，ArrayList觉得优于LinkedList，LinkedList要移动指针。 2、于新增和删除操作add和remove，LinedList比较占优势，ArrayList要移动数据。 3、单条数据插入或删除，ArrayList的速度反而优于LinkedList.原因是：LinkedList的数据结构是三个对象，组大小恰当就会比链表快吧，直接赋值就完了，不用再设置前后指针的值。 若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

如以上文章或链接对你有帮助的话，别忘了在文章结尾处评论哈。你也可以分享哦，让更多的人阅读这篇文章。