Sposoby iteracji po liście w Javie


576

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).


1
Są to niepatologiczne, chociaż możesz również użyć dowolnej z kilku funkcjonalnych bibliotek do przetwarzania kolekcji.
Dave Newton

Czy pytanie dotyczące Listinterfejsu jest specyficzne?
Sotirios Delimanolis

@SotiriosDelimanolis, dla wszystkich celów i celów, tak, jest to specyficzne dla <code> List </code>, ale jeśli istnieją inne ciekawe sposoby pracy z, powiedzmy, <code> Collection </code>, byłbym zainteresowany ich poznaniem.
iX3

@DaveNewton, dzięki za pomysł. Nigdy czegoś takiego nie używałem. Proszę spojrzeć na moje zredagowane pytanie i dać mi znać, jeśli rozumiem, co miałeś na myśli.
iX3

Odpowiedzi:


265

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).


OK, dziękuję, ale jeśli iterator faktycznie zwraca odwołanie do rzeczywistego elementu (nie kopii), to jak mogę go użyć do zmiany wartości na liście? Rozumiem, że jeśli użyję e = iterator.next()a, to e = somethingElsepo prostu ezmieniam, do którego obiektu się odnosi, zamiast zmieniać rzeczywisty sklep, z którego iterator.next()pobrałem wartość.
iX3

@ iX3 - Dotyczy to również iteracji opartej na indeksie; przypisanie nowego obiektu, aby enie zmieniało tego, co jest na liście; musisz zadzwonić list.set(index, thing). Można zmienić zawartość z e(na przykład e.setSomething(newValue)), ale co do zmiany element jest przechowywany w wykazie, jak jesteś iteracja go, trzeba trzymać się z iteracji oparte na indeksie.
Ted Hopp

Dziękuję za to wyjaśnienie; Myślę, że rozumiem to, co teraz mówisz i odpowiednio zaktualizuję moje pytanie / komentarze. Nie ma „kopiowania” jako takiego, ale ze względu na projekt języka w celu wprowadzenia zmian w treści emusiałbym wywołać jedną z emetod, ponieważ przypisanie po prostu zmienia wskaźnik (wybacz moje C).
iX3

Tak więc w przypadku list typów niezmiennych, takich jak Integeri String, nie byłoby możliwe zmienianie zawartości za pomocą metod for-eachlub Iteratormetod - musiałby manipulować samym obiektem listy, aby zastąpić elementy. Czy to prawda?
iX3

@ iX3 - poprawnie. Możesz usunąć elementy z trzecim formularzem (jawny iterator), ale możesz dodawać elementy do listy lub zamieniać elementy tylko na liście, jeśli używasz iteracji opartej na indeksie.
Ted Hopp,

46

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

23

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.


1
Poprawny; to dobra uwaga i zaktualizuję przykład w pytaniu.
iX3

zgodnie z tym postem twoje stwierdzenie jest niepoprawne: która jest bardziej wydajna, dla każdej pętli lub iteratora?
Hibbem,

5
To, co przeczytałem w tym poście, jest dokładnie tym, co powiedziałem ... Co dokładnie czytasz?
amarseillan

20

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

Dzięki, zamierzam w końcu zaktualizować listę u góry o rozwiązania Java 8.
iX3

1
@ eugene82 czy to podejście jest znacznie bardziej wydajne?
nazar_art

1
@ annazar_art Nie zobaczysz znacznej poprawy w stosunku do niczego innego, chyba że użyjesz równoległego strumienia w bardzo dużej kolekcji. Naprawdę jest bardziej skuteczny w sensie tylko uzdrawiającej gadatliwości.
Łotr

7

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

5

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.


1
Dzięki, że o tym wspomniałeś. Nigdy nie patrzyłem na metodę subList. Tak, uważałbym to za patologiczne, ponieważ nie znam żadnych okoliczności, w których korzystniejsze byłoby użycie tego oprócz być może konkursów zaciemniania.
iX3

3
OK. Nie lubię nazywać się „patologicznymi”, więc oto jedno wyjaśnienie: użyłem ich podczas śledzenia lub podążania ścieżkami na drzewach. Jeszcze jeden? Podczas tłumaczenia niektórych programów Lisp na Javę nie chciałem, aby stracili ducha Lisp, i zrobiłem to samo. Głosuj komentarz, jeśli uważasz, że są to prawidłowe, niepatologiczne zastosowania. Potrzebuję grupowego przytulenia !!! :-)
Mario Rossi

Czy ścieżki na drzewach nie są inne niż listy? BTW, nie chciałem nazywać cię ani żadną osobą „patologiczną”, po prostu mam na myśli, że niektóre odpowiedzi na moje pytanie będą zrozumiałe niepraktyczne lub bardzo mało prawdopodobne, aby miały wartość w dobrej praktyce inżynierii oprogramowania.
iX3

@ iX3 Nie martw się; Tylko żartowałem. Ścieżki to listy: „zacznij od katalogu głównego” (oczywiste), „przenieś do drugiego dziecka”, „przejdź do pierwszego dziecka”, „przejdź do czwartego dziecka”. "Zatrzymać". Lub [2,1,4] w skrócie. To jest lista.
Mario Rossi,

Wolałbym utworzyć kopię listy i użyć while(!copyList.isEmpty()){ E e = copyList.remove(0); ... }. To jest bardziej skuteczne niż pierwsza wersja;).
AxelH

2

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

0

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).


0

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
}

3
Pyta, czy istnieją inne sposoby poza opisanymi w pytaniu (które obejmują ten, o którym wspomniałeś)!
ericbn

0

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

Fajne. Czy możesz wyjaśnić, czym różni się to od eugene82odpowiedzi i i_am_zeroodpowiedzi ?
iX3,

@ iX3 ahh. Nie przeczytałem całej listy odpowiedzi. Próbowałeś być pomocny. Czy chcesz, żebym usunął odpowiedź?
Wyniki wyszukiwania Wyniki z sieci Pi

Nie ma dla mnie znaczenia, ale być może mógłbyś to poprawić, porównując i porównując z innymi technikami. Lub jeśli uważasz, że nie wykazuje żadnej nowej techniki, ale może być przydatny jako odniesienie dla innych, być może możesz dodać notatkę wyjaśniającą to.
iX3

-2

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


Prawda ... Chyba jest to technicznie różne, ale zachowanie jest inne tylko wtedy, gdy lista jest pusta, prawda?
iX3

@ ix3 tak, w takim przypadku zachowanie jest gorsze. Nie nazwałbym tego dobrą alternatywą.
CPerkins

Jasne, ale uczciwie, w tym pytaniu nie chodzi o to, co jest „dobre”, a bardziej o to, co jest „możliwe”, więc wciąż doceniam tę odpowiedź.
iX3
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.