LinkedList.contains execution speed

Question

Why Methode LinkedList.contains() runs quickly than such implementation:

for (String s : list) 
   if (s.equals(element))
     return true;
return false;

I don't see great difference between this to implementations(i consider that search objects aren't nulls), same iterator and equals operation

Answer 1

Let's have a look at the source code (OpenJDK version) of java.util.LinkedList

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;
}

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.

The reason for that would be that this indexOf works on the internal structure, using direct field access to iterate, as opposed to the for-each which uses an Iterator<E>, whose methods must also additionally check for things like ConcurrentModificationException etc.

Going back to the source, you will find that the E next() method returned by the Iterator<E> of a LinkedList is the following:

private class ListItr implements ListIterator<E> {
   //...
   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();
  }

This is considerably "busier" than the e = e.next; in LinkedList.contains! The iterator() of a LinkedList is actually a ListIterator, 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 ConcurrentModificationException must be performed, even if there isn't going to be any modification to the list while you're iterating it.

---

Conclusion

So yes, iterating a LinkedList as a client using a for-each (or more straightforwardly, using its iterator()/listIterator()) is more expensive than what the LinkedList itself can do internally. This is to be expected, which is why contains is provided in the first place.

Working internally gives LinkedList tremendous advantage because:

• It can cut corners in defensive checks since it knows that it's not violating any invariants
• It can take shortcuts and work with its internal representations

So what can you learn from this? Familiarize yourself with the API! See what functionalities are already provided; they're likely to be faster than if you've had to duplicate them as a client.

Answer 2

Hi, I decided to test this and came out with some interesting result

import java.util.LinkedList;

public class Contains {

private LinkedList<String> items = new LinkedList<String>();

public Contains(){
    this.addToList();
}

private void addToList(){
    for(int i=0; i<2000; i++){
        this.items.add("ItemNumber" + i);
    }
}

public boolean forEachLoop(String searchFor){
    for(String item : items){
        if(item.equals(searchFor))
            return true;
    }

    return false;
}

public boolean containsMethod(String searchFor){
    if(items.contains(searchFor))
        return true;

    return false;
}

}

and a JUnit testcase:

import static org.junit.Assert.assertEquals;

import org.junit.Test;



public class ContainsTest {

    @Test
    public void testForEachLoop(){
        Contains c = new Contains();

        boolean result = c.forEachLoop("ItemNumber1758");

        assertEquals("Bug!!", true, result);
    }

    @Test
    public void testContainsMethod(){
        Contains c = new Contains();

        boolean result = c.containsMethod("ItemNumber1758");

        assertEquals("Bug!!", true, result);
    }
}

This funny thing is when I run the JUnit test the results are : - testForEachLoop() - 0.014s - testContainsMethod() - 0.025s

Is this true or I am doing something wrong ?