本人java菜鸟，喜欢钻牛角尖，虽然小问题，还是想不通所以不得不问

[nightspirit]

http://zhidao.baidu.com/question/743963713339052332.html?sort=6#answer-1589132274

如题，困扰我好久，请大神指点。

[Linxing]

你还真的是爱钻牛角尖啊，我的看法是没必要，以现在计算机的速度，在乎这些吗，如果这样一味追求性能，ruby都没能用了

[SoloCompany]

这好像是一个常识了吧，LinkedList 基本上是毫无用途的，只有在很特殊很特殊的场合，它才会有能派上用场的地方。对于编程人员来说，只要遵守一个很简单的原则就是了，那就是从来不要使用 LinkedList，除非你很清楚你的数据结构需要 LinkedList 特别优化，否则，任何场合都应该使用 ArrayList

[dndx]

LZ 你需要的是一些基本的数据结构知识，至于 @SoloCompany “LinkedList 基本上毫无用途” 的说法，实在过于可笑，不予反驳。

LinkedList 是一个双向链表，优势在于在链表的任何地方做删减操作时间复杂度为 O(1)，比如你要是需要做一个队列，那么 LinkedList 的这点优势就可以用上。

ArrayList 是一个自动增长的 array ，优势在由于数据在内存上连续存储，随机存取速度为 O(1)，但是在数组中插入和删除数据可能会触发 shift/resize ，所以最坏情况下时间复杂度会达到 O(n)。如果读比删减频繁，那么 ArrayList 会有明显的优势。

至于哪个迭代更快，他们两个迭代的时间复杂度都是 O(1)，如果硬是要分出个胜负，ArrayList 理论上要快一些，因为是连续存储，省了一次指针引用。但是实际应用中这一点区别实在是没有意义，根据你需要的操作，适合的才是最好的。

[ovear]

@dndx 是的，只要频繁删除LinkedList是绝对快于ArrayList的，而且LinkedList可以支持插入到指定位置。ArrayList是一定会进行重新调整的。估计是LinkedList的时间估计是差在寻到对象的时间。

简单地说，ArrayList适合增加删除操作少，且经常随机读取的情况。

[ruoyu0088]

我不懂Java，能不能给一个插入到LinkedList指定位置的例子。这个位置是如何指定的，是一个特殊的位置对象，保存了LinkedList中的某个位置，还是就是一个整数下标？
如果是整数下标的话，LinkedList遍历到那个下标n处的时候不就已经需要n步操作了吗。

[terry0824]

@ruoyu0088 LinkedList与index相关的操作是用指针（不确定这个说法是否准确，就是Node的reference）从head或tail（哪头近从哪头走）遍历到所要找的index处然后进行操作，所以最坏情况就是在最中间，n/2步操作。
http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
LinkedList有一个size()方法可以返回表长度，应该就是有一个field维护元素数量。

[SErHo]

@ruoyu0088 比如你需要实现一个 LRU，就会用到。

[ruoyu0088]

@terry0824 如果需要遍历到index处的话，那么插入到指定index的操作就不是O(1)了吧。

[doing]

你需要一个工具JD-GUI,看源代码实现，应该比较清楚吧

[dndx]

@doing JDK 本来就是开源的，不需要 JD

[nightspirit]

感谢大神@dndx 的详细回答，也多谢大家关注我的问题，我才学java不久，看到书上说的和我的实验结果相反，所以我就一定想要追根究底

[doing]

@dndx 随便啊，只是推荐JD-GUI查看更方便而已，个人意见。

[Narcissu5]

查看下生成的bytecode

现代JVM都是高度优化的，变量其实很多

[SoloCompany]

http://www.onjava.com/pub/a/onjava/2001/05/30/optimization.html

建议楼主看看这个，虽然年代有点老了，但结论对于现代jvm仍然适用

[mx1700]

感觉上不管用何种方式遍历元素，ArrayList都应该比LinkedList快啊
ArrayList的迭代器内部也是通过一个索引下标变量来访问值啊
ArrayList的下标访问肯定比 LinkedList指针引用快

迭代器 比 for 慢是因为每次调用hasNext方法的开销吧

[Ricepig]

@dndx 有些情况下（几率还不低）ArrayList会比LinkedList迭代快得多，这是因为有cache，而ArrayList在内存中是连续的，所以。。。