Какую итерацию я должен использовать для LinkedList? - PullRequest
Новая
       17

Какую итерацию я должен использовать для LinkedList?

2 голосов
/ 23 сентября 2011

Я знаю, что обход LinkedList путем индексации - это плохо, потому что list.get (n) выполняется за линейное время O (n). Таким образом, я не должен использовать индексацию. Я посмотрел на AbstactList.Itr, который возвращается при вызове iterator(), он также использует get(cursor). Я в замешательстве.

Как указал @axtavt, LinkedList.iterator() на самом деле вызывает listIterator(), который возвращает AbstactList.ListItr, который расширяет AbstactList.Itr, и добавляет только реализации интерфейса ListIterator. Таким образом, механизм получения следующего элемента все тот же, что и в AbstactList.Itr. `AbstactList.Itr 'next(); вызывает get(n) в указанном списке.

Ответы [ 6 ]

3 голосов
/ 23 сентября 2011

Цикл foreach очень эффективен и прост: 

List<String> list = new LinkedList<String>();
list.add("First");
list.add("Second");
list.add("Third");
list.add("Fourth");

for(String s : list) {
    System.out.println(s);
}
3 голосов
/ 23 сентября 2011

Наилучшая итерация для любой List (фактически даже любой Iterable) - это для каждого цикла : 

for(Element e : myList){
    // do something
}
2 голосов
/ 23 сентября 2011

LinkedList наследует не только от AbstractList, но и от AbstractSequentialList, который в свою очередь реализует iterator() следующим образом: 

public Iterator<E> iterator() {
    return listIterator();
}

и ListIterator, возвращаемое LinkedList, умело использует последовательный доступ.

Так что, используете ли вы foreach, iterator() или listIterator(), вы всегда имеете дело с одним и тем же типом умного итератора.

2 голосов
/ 23 сентября 2011

Вы должны использовать цикл foreach, если можете - это наиболее эффективно: 

List<Item> myList = ...;

for (Item item : myList) {
  ...
}

Если вам нужно изменить список внутри цикла или просмотреть несколько коллекций в одном цикле, используйте итератор: 

List<Item> myList = ...;
Iterator<Item> it = myList.iterator();

while (it.hasNext()) {
  Item item = it.next();
  ...
}

И если вам нужно перейти назад или что-то еще, связанное со связанными списками, используйте listIterator: 

ListIterator<Item> it = myList.listIterator();
...
0 голосов
/ 23 сентября 2011

Вы можете использовать Iterator, это дает вам более быстрый доступ.Пример кода для списка: 

 List<String> list = new LinkedList<String>();
    list.add("First");
    list.add("Second");
    list.add("Third");
    list.add("Fourth");

    Iterator it = list.iterator();

    while(it.hasNext())
    {
        System.out.println(it.next());
    }
0 голосов
/ 23 сентября 2011

Вы можете использовать итератор, который возвращается методом iterator. Не требуется O (n) времени, чтобы перейти к следующему пункту. Он использует ListIterator реализацию из LinkedList, поэтому он быстрый.

...