ArrayList和LinkedList比较

相同点：

1.都实现了list接口，实现所有可选的列表操作，并且允许所有元素（包括 null），是 Java Collections Framework 的成员。

2.类的实现不是同步的。如果多个线程同时访问列表，而其中至少一个线程从结构上修改了该列表，则它必须保持外部同步。

 

注：保持外部同步一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法来“包装”该列表。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：

List list = Collections.synchronizedList(new LinkedList(...));

List list = Collections.synchronizedList(new ArrayList(...));

 此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：在创建迭代器之后，除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

 

不同点:

1.两者的内部数据结构不同，ArrayList是List 接口的大小可变数组的实现，其内部元素容器是一个Object的数组，

而LinkedList 是List 接口的链接列表实现，内部实际上一个链表的数据结构，其有一个内部类来表示链表.

2.两者的父类不同，也就决定了两者的存储形式不同。 ArrayList继承于 AbstractList,而LinkedList继承于AbstractSequentialList. 两者都实现了List的骨干结构，只是前者的访问形式趋向于 “随机访问”数据存储（如数组），后者趋向于 “连续访问”数据存储（如链接列表）

3.再有就是两者的效率问题， ArrayList基于数组实现，所以毫无疑问可以直接用下标来索引，其索引数据快，插入元素设计到数组元素移动，或者数组扩充，所以插入元素要慢。 LinkedList基于链表结构，插入元素只需要改变插入元素的前后项的指向即可，故插入数据要快，而索引元素需要向前向后遍历，所以索引元素要慢。

4.每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

5.LinkedList实现 Queue 接口，为 add、poll 等提供先进先出队列操作，提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

6.ArrayList中size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

 

 

如何选择？

ArrayList 的内部实现是基于内部数组 Object[] ，所以从概念上讲，它更像数组，但 LinkedList 的内部实现是基于一组连接的记录，所以，它更像一个链表结构，所以，它们在性能上有很大的差别。

在 ArrayList 的前面或中间插入数据时，必须将其后的所有数据相应的后移，这样必然要花费较多时间，所以，当你的操作是在一列数据的后面添加数据而不是在前 面或中间，并且需要随机地访问其中的元素时，使用 ArrayList 会提供比较好的性能；

而访问链表中的某个元素时，就必须从链表的一端开 始沿着连接方向一个一个元素地去查找，直到找到所需的元素为止，所以，当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素 时，就应该使用 LinkedList 了。

如果在编程中，两种情形交替出现，这时，可以考虑 使用 List 这样的通用接口，而不用关心具体的实现，在具体的情形下，它的性能由具体的实现来保证。

案 例： LinkedList 实现堆栈

案 例说明

ArrayList 的查询效率比较高，增删动作的效率比较差，适用于查询比较频繁，增删动作较少的元素管理的集合。 LinkedList 的查询效率低，但是增删效率很高。适用于增删动作的比较频繁，查询次数较少的元素管理集合。

ArrayList ， LinkedList 都是线程不安全的。

实现堆栈 1 ）数组（ ArrayList ，增删效率比较低，不适合）

        2 ） LinkedList （实现堆栈的好方法）

        3 ） java.util.Stack 类， Stack 是 Vector 的子类， Vector 类是一个线程安全的（是一个重量级的类），并继承了 Vector 的方法， Verctor 类和 ArrayList 的功能近乎相同。（不推荐使用 Stack 类来实现堆栈）。