Why is iterating through LinkedList slow?
<p>Java 8</p>

<p>I have quite a large collection (about 100M elements) and I need to iterate through it and do some action. There are two alternatives:</p>

<ol>
<li><p>Iterate through it once and do the entire job (it will complicate the code significantly)</p></li>
<li><p>Iterate through it twice and do half of the job during the first iteration and rest during the second one (this will simplify the code significatly)</p></li>
</ol>

<p>So, I thought that iterating is not so expensive and wrote a simple example to measure it (I don't write benchmarks too often, therefore it may look a bit silly):</p>

<pre><code>    Collection&lt;Double&gt; col = new LinkedList&lt;&gt;();
    for(int i = 0; i &lt; 30000000; i++){
        col.add(Math.sqrt(i + 1));
    }
    long start1 = System.nanoTime();
    Double res = 0.0;
    for(Double d : col){
        res += d + d;
    }
    long end1 = System.nanoTime();
    System.out.println(end1 - start1);
    System.out.println("=================================");
    long start2 = System.nanoTime();
    Double res2 = 0.0;
    for(Double d : col){
        res2 += d;
    }
    for(Double d : col){
        res2 += d;
    }
    long end2 = System.nanoTime();
    System.out.println(end2 - start2);
</code></pre>

<p>The average result is the following:</p>

<p><code>1107881047</code> First </p>

<p><code>2133450162</code> Second (twice as slower)</p>

<p>So, iteration is quite a slow process. But I didn't understand why? I thought we do almost the same amount of work, so the performance would be that much different.</p>

<p>Remarkably, that if I use <code>ArrayList</code> instead of linked list, the result is:</p>

<p><code>3858616604</code> First</p>

<p><code>422297749</code> Second (Ten times faster than the first, twice as faster than in the example above).</p>

<p>Couldn't you explain in a nutshell this performance difference?</p>