Iterowanie po LinkedList

Mamy liste:

List<Integer> numbers = new LinkedList<>(Arrays.asList(1,2,3,4));

W związku z tym, że jest to kolekcja LinkedList złożoność w dostępie do
pojedyńczego elementu to O(n).

Doszedłem więc do wniosku, że:

// bardziej optymalne
for (Integer n: numbers) {
    System.out.println(n);
}

// mniej optymalne
for (int i=0; i<numbers.size(); ++i) {
    System.out.println(numbers.get(i));
}

Drugi wariant (verbose) w moim mniemaniu jest mniej optymalny
gdyż za każdym razem musi przeiterować po elementach aż
dojdzie do tego konkretnego.
Czasem widzę kod gdzie wykorzystywany jest drugi wariant po to aby
mieć indeks. Czy nie byłoby optymalniej wtedy zrobić tak?

int index = 0;
for (Integer n: numbers) {
    System.out.println(n);
    ++index;
}

Zwłaszcza, że często nie wiemy czy pod spodem jest ArrayList
czy LinkedList bo dla tego pierwszego wariant nie miałby znaczenia
poza czytelnością.

No więc odpowiadając na Twoje pytanie; tak, iterowanie...

for (Integer n: numbers) {
    System.out.println(n);
}

jest najbardziej optymalne, dlatego że wykorzystuje wbudowany Iterable w kolekcję; który oczywiście jest zoptymalizowany pod odpowiednią implementację. Z tego powodu nie ma mowy o żadnym "indexie", ani o liczniku; ponieważ Iterable w ogóle nie ma takiego bytu; on po prostu zapewnia sekwencyjny, płaski dostęp do elementów. Z tego powodu foreach nie udostępnia żadnego licznika/klucza.

Jednakże, dostęp do numeru;indexu tablicy w takim foreach'u, to przyznam się pomysł dosyć dziwny; po co niby byłby Ci taki indeks? Jedyne do czego mógłbyś to użyć, to sprawdzić czy element jest pierwszy czy ostatni - może. Ale jeśli masz LinkedList; to mógłbyś po prostu porównać elementy, bo LinkedList Ci daje dostęp do nich.

Jeśli miałbyś porównywać indeksy iterując po liście; to dla mnie to jest sygnał złego design'u, i trzeba by się zastanowić nad architekturą.

Natomiast jeśli faktycznie miałbym się "dobrać" do klucza, to dla mnie oczywistym jest ostatnie podejście, czyli swoja zmienna, inkrementowana co obrót pętli. Po co miałbym używać swojego counter'a do odczytywania get(i)? ;| Nie ma to żadnego sensu. Nie wiem kto Ci powiedział:

Czasem widzę kod gdzie wykorzystywany jest drugi wariant po to aby mieć indeks.

...ale ktokolwiek wpadł na taki pomysł nie był zbyt dobrym programistą.

@lookacode1: trochę uzupełnię odpowiedź @TomRiddle.

Faktycznie samo iterowanie po liście lepiej robić for-eachem i iterowanie z jednoczesnym trzymaniem indeksu trochę mija się z celem. Siłą LinkedList jest to, że zmiany w środku możesz robić na żywca, inaczej po prostu lepiej skorzystać z ArrayList.

Natomiast jeśli chcesz skorzystać z tej zalety LinkedList i np. mając listę Stringów: "A", "B", "C", "D", "E"

1. Usunąć z niej elementy "A", "C" i "E"
2. Przed "D" wstawić "G"

To zamiast korzystać z indeksów lepiej skorzystać z ListIterator:

Set<String> elementsToDelete = Set.of("A", "C", "E");

List<String> elements = Stream.of("A", "B", "C", "D", "E")
        .collect(Collectors.toCollection(LinkedList::new));

ListIterator<String> iterator = elements.listIterator();
String element;
while (iterator.hasNext()) {
        element = iterator.next();
        if (element.equals("D")) {
                iterator.previous();
                iterator.add("G");
                iterator.next();
        }

        if (elementsToDelete.contains(element)) {
                iterator.remove();
        }
}
System.out.println(elements);

@wartek01: wersja alternatywna, trochę bardziej czytelna bez modyfikacji wejścia:

List<String> newElements = elements.stream()
	 .flatMap(entry -> "D".equals(entry) ? Stream.of("G", entry) : Stream.of(entry))
	 .filter(Predicate.not(elementsToDelete::contains)).collect(Collectors.toList()); 

https://ideone.com/1XDbln

@vpiotr: twój kod jest czytelniejszy i pewnie w 80% przypadków się lepiej sprawdzi - tam gdzie nie liczy się wydajność. Tyle tylko, że ja nie piszę o takich przypadkach. Dosyć jasno napisałem, że właśnie zaletą LinkedList jest to, że można ją wydajnie modyfikować - a to jest zaleta, która się liczy gdy normalne praktyki CRUDowe należy odłożyć do schowka.

Tu jeszcze mini uwaga
normalne biblioteki do kolekcji mają typowo operację w stylu mapIndexed lub zipWithIndex itp.

https://www.javadoc.io/doc/io.vavr/vavr/latest/io/vavr/collection/List.html

Polecam nie używać kolekcji z java.util w "typowym kodzie". (Czyli o ile nie robisz czegoś nietypowego i walczysz o cykle).

@wartek01 @vpiotr
Tu nie chodzi o to, że muszę manipulować tą listą wiem, że do tego lepiej nadaje się LinkedList tylko chodzi o przeiterowanie po niej.
Drugi wariant, który podałem jest lepszy bo złożoność zawsze będzie O(n) natomiast pierwszy w zależności od tego jaka lista jest pod
spodem jeśli LinkedList to O(n^2) jeśli ArrayList O(n) bo dostęp do pojedyńczego elementu w tej liście ma złożoność O(1).

@jarekr000000: Tak wgl doszedłem do wniosku, że kolekcje immutable w javie są bez sensu
bo rzucają UnsupportedOperationException jak wywołujesz np. add na liście a de facto powinny
wgl nie wystawiać takiego interfejsu.

@lookacode1: to o czym piszesz to nie są kolekcje immutable. To taka bryndza z java.util. - roboczo nazywamy to readonly choć java.util.faktycznie nazywa to immutable.

Zapomnij o java.util.. To w większości niezdrowy pakiet, a kolekcje to tylko kawałek. (Są tam ciekawe klasy i niektóre nawet użyteczne - ale to raczej wypadki przy pracy).

@lookacode1: Może po prostu powiedz co chcesz zrobić; to powiemy Ci jak to najlepiej ugryść.