Sposoby iteracji po liście w Javie

Będąc nieco nowym językiem Java, próbuję zapoznać się ze wszystkimi sposobami (a przynajmniej niepatologicznymi), które można iterować po liście (lub innych kolekcjach) oraz zaletami i wadami każdego z nich.

Biorąc pod uwagę List<E> listobiekt, znam następujące sposoby przechodzenia przez wszystkie elementy:

Podstawowy dla pętli (oczywiście istnieją również odpowiedniki while/ do whilepętle)

// Not recommended (see below)!
for (int i = 0; i < list.size(); i++) {
    E element = list.get(i);
    // 1 - can call methods of element
    // 2 - can use 'i' to make index-based calls to methods of list

    // ...
}

Uwaga: Jak zauważył @amarseillan, ta forma jest kiepskim wyborem dla iteracji w porównaniu z Lists, ponieważ faktyczna implementacja getmetody może nie być tak wydajna jak w przypadku korzystania z Iterator. Na przykład LinkedListimplementacje muszą przechodzić przez wszystkie elementy poprzedzające i, aby uzyskać i-ty element.

W powyższym przykładzie Listimplementacja nie może „zapisać swojego miejsca”, aby zwiększyć wydajność przyszłych iteracji. Dla a ArrayListtak naprawdę nie ma to znaczenia, ponieważ złożoność / koszt getto stały czas (O (1)), podczas gdy dla a LinkedListjest proporcjonalny do wielkości listy (O (n)).

Aby uzyskać więcej informacji na temat złożoności obliczeniowej wbudowanych Collectionsimplementacji, sprawdź to pytanie .

Ulepszone dla pętli (ładnie wyjaśnione w tym pytaniu )

for (E element : list) {
    // 1 - can call methods of element

    // ...
}

Iterator

for (Iterator<E> iter = list.iterator(); iter.hasNext(); ) {
    E element = iter.next();
    // 1 - can call methods of element
    // 2 - can use iter.remove() to remove the current element from the list

    // ...
}

ListIterator

for (ListIterator<E> iter = list.listIterator(); iter.hasNext(); ) {
    E element = iter.next();
    // 1 - can call methods of element
    // 2 - can use iter.remove() to remove the current element from the list
    // 3 - can use iter.add(...) to insert a new element into the list
    //     between element and iter->next()
    // 4 - can use iter.set(...) to replace the current element

    // ...
}

Funkcjonalna Java

list.stream().map(e -> e + 1); // Can apply a transformation function for e

Iterable.forEach , Stream.forEach ...

(Metoda mapy z Stream API Java 8 (patrz odpowiedź @ i_am_zero).)

W klasach Java 8, które implementują Iterable(na przykład wszystkie Lists), istnieje teraz forEachmetoda, której można użyć zamiast instrukcji pętli for pokazanej powyżej. (Oto kolejne pytanie, które zapewnia dobre porównanie).

Arrays.asList(1,2,3,4).forEach(System.out::println);
// 1 - can call methods of an element
// 2 - would need reference to containing object to remove an item
//     (TODO: someone please confirm / deny this)
// 3 - functionally separates iteration from the action
//     being performed with each item.

Arrays.asList(1,2,3,4).stream().forEach(System.out::println);
// Same capabilities as above plus potentially greater
// utilization of parallelism
// (caution: consequently, order of execution is not guaranteed,
// see [Stream.forEachOrdered][stream-foreach-ordered] for more
// information about this).

Jakie są inne sposoby, jeśli istnieją?

(BTW, moje zainteresowanie wcale nie wynika z chęci optymalizacji wydajności ; chcę tylko wiedzieć, jakie formy są dostępne jako programista).

Trzy formy zapętlenia są prawie identyczne. Ulepszona forpętla:

for (E element : list) {
    . . .
}

jest, zgodnie ze specyfikacją języka Java , identyczny z wyraźnym zastosowaniem iteratora z tradycyjną forpętlą. W trzecim przypadku możesz zmodyfikować zawartość listy tylko poprzez usunięcie bieżącego elementu, a następnie tylko wtedy, gdy zrobisz to za pomocą samej removemetody iteratora. Dzięki iteracji opartej na indeksie możesz dowolnie modyfikować listę. Jednak dodawanie lub usuwanie elementów poprzedzających bieżący indeks grozi pomijaniem elementów w pętli lub przetwarzaniem tego samego elementu wiele razy; podczas dokonywania takich zmian należy odpowiednio dostosować indeks pętli.

We wszystkich przypadkach elementjest odwołaniem do rzeczywistego elementu listy. Żadna z metod iteracji nie tworzy kopii niczego na liście. Zmiany stanu wewnętrznego elementzawsze będą widoczne w stanie wewnętrznym odpowiedniego elementu na liście.

Zasadniczo istnieją tylko dwa sposoby iteracji po liście: za pomocą indeksu lub iteratora. Ulepszona pętla for to po prostu skrót składniowy wprowadzony w Javie 5, aby uniknąć nudy jawnego definiowania iteratora. Dla obu stylów, można wymyślić zasadniczo błahe wariacji użyciem for, whileczy do whilebloki, ale wszystkie one sprowadzają się do tego samego (albo raczej dwie rzeczy).

EDYCJA: Jak wskazuje @ iX3 w komentarzu, możesz użyć a, ListIteratoraby ustawić bieżący element listy podczas iteracji. Będziesz musiał użyć List#listIterator()zamiast List#iterator()zainicjować zmienną pętli (która oczywiście musiałaby zostać zadeklarowana jako ListIteratora nie Iterator).

Przykład każdego rodzaju wymienionego w pytaniu:

ListIterationExample.java

import java.util.*;

public class ListIterationExample {

     public static void main(String []args){
        List<Integer> numbers = new ArrayList<Integer>();

        // populates list with initial values
        for (Integer i : Arrays.asList(0,1,2,3,4,5,6,7))
            numbers.add(i);
        printList(numbers);         // 0,1,2,3,4,5,6,7

        // replaces each element with twice its value
        for (int index=0; index < numbers.size(); index++) {
            numbers.set(index, numbers.get(index)*2); 
        }
        printList(numbers);         // 0,2,4,6,8,10,12,14

        // does nothing because list is not being changed
        for (Integer number : numbers) {
            number++; // number = new Integer(number+1);
        }
        printList(numbers);         // 0,2,4,6,8,10,12,14  

        // same as above -- just different syntax
        for (Iterator<Integer> iter = numbers.iterator(); iter.hasNext(); ) {
            Integer number = iter.next();
            number++;
        }
        printList(numbers);         // 0,2,4,6,8,10,12,14

        // ListIterator<?> provides an "add" method to insert elements
        // between the current element and the cursor
        for (ListIterator<Integer> iter = numbers.listIterator(); iter.hasNext(); ) {
            Integer number = iter.next();
            iter.add(number+1);     // insert a number right before this
        }
        printList(numbers);         // 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

        // Iterator<?> provides a "remove" method to delete elements
        // between the current element and the cursor
        for (Iterator<Integer> iter = numbers.iterator(); iter.hasNext(); ) {
            Integer number = iter.next();
            if (number % 2 == 0)    // if number is even 
                iter.remove();      // remove it from the collection
        }
        printList(numbers);         // 1,3,5,7,9,11,13,15

        // ListIterator<?> provides a "set" method to replace elements
        for (ListIterator<Integer> iter = numbers.listIterator(); iter.hasNext(); ) {
            Integer number = iter.next();
            iter.set(number/2);     // divide each element by 2
        }
        printList(numbers);         // 0,1,2,3,4,5,6,7
     }

     public static void printList(List<Integer> numbers) {
        StringBuilder sb = new StringBuilder();
        for (Integer number : numbers) {
            sb.append(number);
            sb.append(",");
        }
        sb.deleteCharAt(sb.length()-1); // remove trailing comma
        System.out.println(sb.toString());
     }
}

Pętla podstawowa nie jest zalecana, ponieważ nie znasz implementacji listy.

Jeśli była to lista połączona, każde połączenie z

list.get(i)

będzie iterować po liście, powodując złożoność czasową N ^ 2.

Iteracja w stylu JDK8:

public class IterationDemo {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3);
        list.stream().forEach(elem -> System.out.println("element " + elem));
    }
}

W Javie 8 mamy wiele sposobów na iterację klas kolekcji.

Korzystanie z Iterable forEach

Kolekcje, które implementują Iterable(na przykład wszystkie listy) mają teraz forEachmetodę. Możemy użyć referencji metod wprowadzonych w Javie 8.

Arrays.asList(1,2,3,4).forEach(System.out::println);

Korzystanie ze strumieni dla forEach i forEachOrders

Możemy również iterować listę, używając Stream jako:

Arrays.asList(1,2,3,4).stream().forEach(System.out::println);
Arrays.asList(1,2,3,4).stream().forEachOrdered(System.out::println);

Powinny wolimy forEachOrderedponad forEachponieważ zachowanie forEachjest wyraźnie niedeterministyczny gdzie jak forEachOrderedwykonuje czynność dla każdego elementu tego strumienia, w celu napotkać strumienia jeśli strumień ma określony porządek spotkania. ForEach nie gwarantuje, że zamówienie zostanie zachowane.

Zaletą strumieni jest to, że możemy również korzystać z równoległych strumieni tam, gdzie jest to właściwe. Jeśli celem jest jedynie wydrukowanie elementów niezależnie od zamówienia, możemy użyć strumienia równoległego jako:

Arrays.asList(1,2,3,4).parallelStream().forEach(System.out::println);

Nie wiem, co uważasz za patologiczne, ale pozwól, że przedstawię alternatywy, których wcześniej nie widziałeś:

List<E> sl= list ;
while( ! sl.empty() ) {
    E element= sl.get(0) ;
    .....
    sl= sl.subList(1,sl.size());
}

Lub jego wersja rekurencyjna:

void visit(List<E> list) {
    if( list.isEmpty() ) return;
    E element= list.get(0) ;
    ....
    visit(list.subList(1,list.size()));
}

Również rekursywna wersja klasycznego for(int i=0...:

void visit(List<E> list,int pos) {
    if( pos >= list.size() ) return;
    E element= list.get(pos) ;
    ....
    visit(list,pos+1);
}

Wspominam o nich, ponieważ jesteś „nieco nowy w Javie” i może to być interesujące.

Możesz używać forEach od Java 8:

 List<String> nameList   = new ArrayList<>(
            Arrays.asList("USA", "USSR", "UK"));

 nameList.forEach((v) -> System.out.println(v));

Do wyszukiwania wstecznego należy użyć:

for (ListIterator<SomeClass> iterator = list.listIterator(list.size()); iterator.hasPrevious();) {
    SomeClass item = iterator.previous();
    ...
    item.remove(); // For instance.
}

Jeśli chcesz poznać pozycję, użyj iteratora.previousIndex (). Pomaga również napisać wewnętrzną pętlę, która porównuje dwie pozycje na liście (iteratory nie są równe).

Tak, wymienionych jest wiele alternatyw. Najłatwiejszym i najczystszym byłoby użycie ulepszonego forwyrażenia, jak poniżej. Jest Expressionto pewnego rodzaju, który jest iterowalny.

for ( FormalParameter : Expression ) Statement

Na przykład, aby iterować przez listę <String> id, możemy po prostu tak,

for (String str : ids) {
    // Do something
}

W java 8można użyć List.forEach()metody z lambda expressiondo iteracji po liście.

import java.util.ArrayList;
import java.util.List;

public class TestA {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("Apple");
        list.add("Orange");
        list.add("Banana");
        list.forEach(
                (name) -> {
                    System.out.println(name);
                }
        );
    }
}

Zawsze możesz zamienić pierwszy i trzeci przykład za pomocą pętli while i trochę więcej kodu. Daje to korzyść z możliwości korzystania z do-while:

int i = 0;
do{
 E element = list.get(i);
 i++;
}
while (i < list.size());

Oczywiście tego rodzaju rzeczy mogą powodować wyjątek NullPointerException, jeśli list.size () zwraca 0, ponieważ zawsze jest wykonywane przynajmniej raz. Można to naprawić, sprawdzając, czy element jest pusty przed użyciem jego atrybutów / metod. Mimo to korzystanie z pętli for jest o wiele prostsze i łatwiejsze