Када користите колекције, у којим случајевима је брже обилазак: у ArrayList или у LinkedList?

Iteracija elemenata u kolekcijama ArrayList i LinkedList u Javi razlikuje se po performansama zbog njihove interne strukture.

• ArrayList se zasniva na nizu, pa je pristup elementu po indeksu u vremenu O(1). Iteracija pomoću for petlje sa indeksima je veoma brza.
• LinkedList je dvostruko povezana lista, gde je pristup elementu po indeksu zahteva prolazak kroz listu od početka ili kraja, što traje O(n) vremena.

Zbog toga je prolazak kroz sve elemente pomoću iteratora ili foreach petlje otprilike isti za obe kolekcije, ali ako se prolazi koristeći indekse (npr. get(i) u petlji), tada će ArrayList biti znatno brži.

Primer:

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();
// popunjavanje listi

// Brzo prolaz u ArrayList
for (int i = 0; i < arrayList.size(); i++) {
    String item = arrayList.get(i); // O(1)
}

// Sporo prolaz u LinkedList koristeći indekse
for (int i = 0; i < linkedList.size(); i++) {
    String item = linkedList.get(i); // O(n)
}

// Preporučuje se korišćenje iteratora ili foreach za LinkedList
for (String item : linkedList) {
    // obrada elementa
}

Tako je prolaz brži u ArrayList, posebno ako je potreban pristup po indeksu.