Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Let's have a look at <a href="http://www.google.com/codesearch/p?hl=en#av_p04Hv9fs/src/share/classes/java/util/LinkedList.java&amp;l=193" rel="noreferrer">the source code</a> (OpenJDK version) of <code>java.util.LinkedList</code></p> <pre><code>public boolean contains(Object o) { return indexOf(o) != -1; } public int indexOf(Object o) { int index = 0; if (o==null) { /* snipped */ } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) return index; index++; } } return -1; } </code></pre> <p>As you can see, this is a linear search, just like the for-each solution, so it's NOT asymptotically faster. It'd be interesting to see how your numbers grow with longer lists, but it's likely to be a constant factor slower.</p> <p>The reason for that would be that this <code>indexOf</code> works on the internal structure, using direct field access to iterate, as opposed to the for-each which uses an <code>Iterator&lt;E&gt;</code>, whose methods must also additionally check for things like <code>ConcurrentModificationException</code> etc.</p> <p>Going back to the source, you will find that the <code>E next()</code> method returned by the <code>Iterator&lt;E&gt;</code> of a <code>LinkedList</code> is the following:</p> <pre><code>private class ListItr implements ListIterator&lt;E&gt; { //... public E next() { checkForComodification(); if (nextIndex == size) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.element; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } </code></pre> <p>This is considerably "busier" than the <code>e = e.next;</code> in <code>LinkedList.contains</code>! The <code>iterator()</code> of a <code>LinkedList</code> is actually a <a href="http://java.sun.com/javase/6/docs/api/java/util/ListIterator.html" rel="noreferrer"><code>ListIterator</code></a>, which has richer features. They aren't needed in your for-each loop, but unfortunately you have to pay for them anyway. Not to mention all those defensive checks for <code>ConcurrentModificationException</code> must be performed, even if there isn't going to be any modification to the list while you're iterating it.</p> <hr> <h3>Conclusion</h3> <p>So yes, iterating a <code>LinkedList</code> as a client using a for-each (or more straightforwardly, using its <code>iterator()/listIterator()</code>) is more expensive than what the <code>LinkedList</code> itself can do internally. This is to be expected, which is why <code>contains</code> is provided in the first place.</p> <p>Working internally gives <code>LinkedList</code> tremendous advantage because:</p> <ul> <li>It can cut corners in defensive checks since it knows that it's not violating any invariants</li> <li>It can take shortcuts and work with its internal representations</li> </ul> <p>So what can you learn from this? <strong>Familiarize yourself with the API!</strong> See what functionalities are already provided; they're likely to be faster than if you've had to duplicate them as a client.</p>
    singulars
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. This table or related slice is empty.
    2. VO
      singulars
      1. This table or related slice is empty.
    3. VO
      singulars
      1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload