Сравнение двух LinkedList <String>с ListIterator по сравнению с for и get (int index)

Question

У меня есть два объекта LinkedList, которые всегда имеют одинаковый размер. Я хочу сравнить их, чтобы увидеть, идентичны ли они по содержанию. Каковы общие последствия для производительности и стиля создания ListIterator для каждого списка и использования цикла while hasNext по сравнению с использованием счетчика (int i) и итерацией от 0 до connectedlist.size () с использованием connectedlist.get (i) для получения и сравнения ценности? Есть ли лучший способ, которым я пропускаю?

Единственное, о чем я могу думать, это то, что метод ListIterator может быть лучше в том смысле, что я мог бы легче поменять другой список Comparable позже (не то, что я планирую это). Я не знаю, как эти двое выглядят под капотом, поэтому я не уверен, как бы я сравнил их по производительности.

Answer 1

Как оказалось, AbstractList.equals() (который использует LinkedList) сделает это автоматически, так что используйте это. Код:

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

Так что не изобретай велосипед.

Последнее замечание: не используйте get(index) для итерации по LinkedList. Это O (n) доступ (O (1) для ArrayList), поэтому LinkedList обход с использованием get(index) будет O (n ² ).

Answer 2

Случайный доступ к LinkedList имеет ужасную производительность (он должен начинаться с одного конца и повторно вызывать next или аналогичный), поэтому ListIterator будет быстрее.

Answer 3

get(n) для связанных списков не является постоянной операцией для классов, расширяющих AbstractSequentialList; это O(n). From AbstractSequentialList # get (int index) :

Эта реализация сначала получает итератор списка, указывающий на индексированный элемент (с listIterator(index)). Затем он получает элемент с помощью ListIterator.next и возвращает его.

Как правило, вы не хотите использовать произвольный доступ к коллекциям, в которых не реализован интерфейс маркера java.util.RandomAccess.

Как правило, реализация List должна реализовывать этот интерфейс, если для типичных экземпляров класса этот цикл:

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

работает быстрее, чем этот цикл:

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

Начиная с Java SE 6, классы реализации: ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector.