ArrayList与LinkedList
我在以前的post上说这个：
对于LinkedList
- 得到是O（n）
- 加上是O（1）
- 删除是O（n）
- Iterator.remove是O（1）
对于ArrayList
- 得到是O（1）
- add是O（1）分期付款，但O（n）最坏的情况，因为数组必须resize和复制
- 删除是O（n）
所以通过看这个，我得出的结论是，如果我只需要对我的集合中的5000000元素进行顺序插入，则LinkedList将超出ArrayList 。
如果我只是通过迭代来获取集合中的元素，即不在中间抓取元素， LinkedList仍然会超出ArrayList。
现在为了validation我的上述两个陈述，我写了下面的示例程序…但是我惊讶于我的上述陈述被certificate是错误的。
在这两种情况下ArrayList Linkedlist 。 花费比LinkedList更less的时间来添加以及从Collection中获取它们。 有什么我做错了，或者有关LinkedList和ArrayList的初始语句不适用于大小为5000000的集合吗？
我提到了大小，因为如果我将元素数量减less到50000， LinkedListperformance更好，并且初始语句成立。
long nano1 = System.nanoTime(); List<Integer> arr = new ArrayList(); for(int i = 0; i < 5000000; ++i) { arr.add(i); } System.out.println( (System.nanoTime() - nano1) ); for(int j : arr) { ; } System.out.println( (System.nanoTime() - nano1) ); long nano2 = System.nanoTime(); List<Integer> arrL = new LinkedList(); for(int i = 0; i < 5000000; ++i) { arrL.add(i); } System.out.println( (System.nanoTime() - nano2) ); for(int j : arrL) { ; } System.out.println( (System.nanoTime() - nano2) );
请记住，大O复杂性描述渐近行为，可能不反映实际执行速度。 它描述了每个操作的成本如何随着列表的大小而增长，而不是每个操作的速度。 例如，下面的add实现是O（1）但不是快速的：
public class MyList extends LinkedList { public void add(Object o) { Thread.sleep(10000); super.add(o); } }
我怀疑在你的情况下ArrayList性能良好，因为它相当积极地增加了内部缓冲区大小，所以不会有大量的重新分配。 当缓冲区不需要resizeArrayList将有更快的add 。
在进行这种分析时，您还需要非常小心。 我build议你改变你的分析代码做一个热身阶段（所以JIT有机会做一些优化而不影响你的结果），并平均结果在一些运行。
private final static int WARMUP = 1000; private final static int TEST = 1000; private final static int SIZE = 500000; public void perfTest() { // Warmup for (int i = 0; i < WARMUP; ++i) { buildArrayList(); } // Test long sum = 0; for (int i = 0; i < TEST; ++i) { sum += buildArrayList(); } System.out.println("Average time to build array list: " + (sum / TEST)); } public long buildArrayList() { long start = System.nanoTime(); ArrayList a = new ArrayList(); for (int i = 0; i < SIZE; ++i) { a.add(i); } long end = System.nanoTime(); return end - start; } ... same for buildLinkedList
（请注意， sum可能会溢出，您可能会更好地使用System.currentTimeMillis() ）。
编译器也可以优化掉空的get循环。 确保循环实际上做了一些事情，以确保正确的代码被调用。
这是IMO的一个糟糕的基准。
- 需要多次重复循环才能预热jvm
- 需要在迭代循环中做一些事情，或者可以优化数组
-
ArrayListresize，这是昂贵的。 如果你已经构造了ArrayList作为new ArrayList(500000)你将一举构build，然后所有的分配将是相当便宜的（一个预分配支持的数组） - 你不指定你的内存JVM – 它应该用-xMs == -Xmx（一切预分配）来运行，并且足够高以至于不可能触发GC
- 这个基准并没有涵盖LinkedList的最不愉快的方面 – 随机访问。 （一个迭代器不一定是相同的东西）。 如果你把一个大集合的大小的10％作为
list.get一个随机select，你会发现linkedlists对于抓取除第一个或最后一个元素之外的任何东西都是可怕的。
对于数组列表：jdk get就是你所期望的：
public E get(int index) { RangeCheck(index); return elementData[index]; }
（基本上只是返回索引数组元素。，
对于一个链表：
public E get(int index) { return entry(index).element; }
看起来相似？ 不完全的。 入口是一种方法不是一个原始数组，并看看它必须做什么：
private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
没错，如果你要求说list.get(250000) ，那就得从头开始，反复迭代下一个元素。 250000左右的访问（有一个优化的代码，它在头部或尾部开始取决于哪个将访问较less）。
ArrayList比LinkedList更简单的数据结构。 一个ArrayList在连续的内存位置有一个指针数组。 只有在数组扩展超出其分配的大小时才需要重新创build。
LinkedList由一系列节点组成; 每个节点分开分配，并具有前向和后向指向其他节点的指针。
那么这是什么意思？ 除非你需要插入中间，拼接，删除中间等ArrayList通常会更快。 它需要更less的内存分配，具有更好的参考位置（这对于处理器caching很重要）等等。
要理解为什么你得到的结果不会与“大O”表征相抵触。 我们需要回到最初的原则。 即定义 。
令f（x）和g（x）是在实数的一些子集上定义的两个函数。 一个写道
f(x) = O(g(x)) as x -> infinity当且仅当对于足够大的x值，f（x）至多是绝对值乘以g（x）的常数。 即，当且仅当存在正实数M和实数x0时，f（x）= O（g（x））
|f(x)| <= M |g(x)| for all x > x_0.在许多情况下，我们对增长率感兴趣的variablesx变为无穷大的假设是没有说明的，并且更简单地写成f（x）= O（g（x））。
因此，语句add1 is O(1) ，意味着在N大小的列表上的add1操作的时间成本趋于恒定的C add1，因为N趋于无穷大。
并且语句add2 is O(1) amortized over N operations ，意味着N个add2操作序列之一的平均时间成本趋于恒定C add2，因为N趋于无穷大。
什么是不说的是那些常量C add1和C add2是什么。 实际上，LinkedList比基准中的ArrayList慢的原因是C add1大于C add2 。
大的O符号并不能预测绝对甚至相对的性能。 所有它预测的是性能函数的形状 ，因为控制variables变得非常大。 知道这一点很有用，但并不能告诉你所有你需要知道的东西。
大O符号不是绝对的时间安排，而是相对的时间安排，你不能把一个algorithm的数目和另一个algorithm的数目进行比较。
你只能得到相同的algorithm如何反应增加或减less元组数量的信息。
一个algorithm可能需要一个小时才能完成一个操作，而两个操作需要两个小时，并且是O（n），另一个algorithm也是O（n），一个操作需要一个毫秒，两个操作需要两个毫秒。
使用JVM测量的另一个问题是热点编译器的优化。 JIT编译器可以消除无效循环。
第三件要考虑的是操作系统和JVM，同时使用caching并运行垃圾收集。
很难find一个好的LinkedList用例。 如果你只需要使用Dequeu接口，你应该使用ArrayDeque。 如果你真的需要使用List接口，你会经常听到总是使用ArrayList的build议，因为LinkedList在访问一个随机元素的行为非常糟糕。
不幸的是，如果必须删除或插入列表的开头或中间的元素，则ArrayList会有性能问题。
然而，有一个名为GapList的新列表实现，它结合了ArrayList和LinkedList的优点。 它被devise为ArrayList和LinkedList的插入replace，因此实现了接口List和Deque。 同样所有由ArrayList提供的公共方法都被实现（ensureCapacty，trimToSize）。
GapList的实现保证了按索引对元素进行高效的随机访问（如ArrayList所做的那样），同时还有效地向列表头部和尾部添加和移除元素（如LinkedList所做的那样）。
有关GapList的更多信息，请参阅http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list 。
O符号分析提供了重要的信息，但它有其局限性。 根据定义，O符号分析认为每个操作的执行时间大致相同，这是不正确的。 正如@seand指出的，链接列表内部使用更复杂的逻辑来插入和获取元素（看看源代码，你可以在你的IDE中按Ctrl +单击）。 ArrayList内部只需要将元素插入到数组中，并在一段时间内增加其大小（甚至是o（n）操作，实际上可以很快完成）。
干杯
您可以分开添加或删除作为一个两步操作。
LinkedList ：如果你添加一个元素到索引n，你可以将指针从0移动到n-1，然后你可以执行你所谓的O（1）添加操作。 删除操作是一样的。
ArraryList ：ArrayList实现了RandomAccess接口，这意味着它可以访问O（1）中的一个元素。
如果在索引n中添加一个元素，它可以进入O（1）中的n-1索引，在n-1之后移动元素，在n个时隙中添加元素。
移动操作由一个称为System.arraycopy的本地方法执行，速度非常快。
public static void main(String[] args) { List<Integer> arrayList = new ArrayList<Integer>(); for (int i = 0; i < 100000; i++) { arrayList.add(i); } List<Integer> linkList = new LinkedList<Integer>(); long start = 0; long end = 0; Random random = new Random(); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { linkList.add(random.nextInt(100000), 7); } end = System.currentTimeMillis(); System.out.println("LinkedList add ,random index" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { arrayList.add(random.nextInt(100000), 7); } end = System.currentTimeMillis(); System.out.println("ArrayList add ,random index" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { linkList.add(0, 7); } end = System.currentTimeMillis(); System.out.println("LinkedList add ,index == 0" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { arrayList.add(0, 7); } end = System.currentTimeMillis(); System.out.println("ArrayList add ,index == 0" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { linkList.add(i); } end = System.currentTimeMillis(); System.out.println("LinkedList add ,index == size-1" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { arrayList.add(i); } end = System.currentTimeMillis(); System.out.println("ArrayList add ,index == size-1" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { linkList.remove(Integer.valueOf(random.nextInt(100000))); } end = System.currentTimeMillis(); System.out.println("LinkedList remove ,random index" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { arrayList.remove(Integer.valueOf(random.nextInt(100000))); } end = System.currentTimeMillis(); System.out.println("ArrayList remove ,random index" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { linkList.remove(0); } end = System.currentTimeMillis(); System.out.println("LinkedList remove ,index == 0" + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { arrayList.remove(0); } end = System.currentTimeMillis(); System.out.println("ArrayList remove ,index == 0" + (end - start)); }
