Comparing two LinkedList<String> with ListIterator versus for loop and get(int index)

Question

I have two LinkedList objects that are always of the same size. I want to compare them to see if they are identical in content. What are the general performance and style implications of creating a ListIterator for each list and using a while hasNext loop versus using a counter (int i) and iterating from 0 to linkedlist.size() using linkedlist.get(i) to get and compare the values? Is there a better way that I'm overlooking?

The only thing I can think of is that the ListIterator method may be better in that I could more easily swap in another Comparable list later (not that I plan on it). I don't know what the two look like under the hood, so I'm not sure how I would compare them performance-wise.

Answer 1

As it turns out AbstractList.equals() (which LinkedList uses) will do this automatically so use that. The code is:

public boolean equals(Object o) {
  if (o == this)
    return true;
  if (!(o instanceof List))
    return false;

  ListIterator<E> e1 = listIterator();
  ListIterator e2 = ((List) o).listIterator();
  while (e1.hasNext() && e2.hasNext()) {
    E o1 = e1.next();
    Object o2 = e2.next();
    if (!(o1 == null ? o2 == null : o1.equals(o2)))
      return false;
  }
  return !(e1.hasNext() || e2.hasNext());
}

So don't reinvent the wheel.

One final note: don't use get(index) to iterate over a LinkedList. It's O(n) access (O(1) for an ArrayList) so a LinkedList traversal using get(index) will be O(n²).

Answer 2

Random access into a LinkedList has horrible performance (it needs to start at one end and invoke next or similar repeatedly), so the ListIterator would be faster.

Answer 3

get(n) for linked lists is not a constant operation for classes that extend AbstractSequentialList; it's O(n). From AbstractSequentialList#get(int index):

This implementation first gets a list iterator pointing to the indexed element (with listIterator(index)). Then, it gets the element using ListIterator.next and returns it.

Generally you don't want to do random access on collections that don't implement the marker interface java.util.RandomAccess.

As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:

 for (int i=0, n=list.size(); i < n; i++)
     list.get(i);

runs faster than this loop:

 for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

As of Java SE 6, the implementing classes are ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector.