Kogudes kogumikke kasutades, millistel juhtudel on läbimine kiirem: ArrayList või LinkedList?

Java kogumikes ArrayList ja LinkedList elementide kordamine erineb nende sisemise struktuuri tõttu.

• ArrayList põhineb massiivil, seega juurdepääs elemendile indeksi järgi toimub O(1) ajal. Indeksiga for-tsükli kasutamine on väga kiire.
• LinkedList on kahetipiline ühendatud nimekiri, kus indeksi järgi elemendile juurdepääs nõuab nimekirja läbimist algusest või lõpust, mis võtab aega O(n).

Seetõttu on kõigi elementide läbimine iteratori või foreach abil umbes sama mõlema kogumi puhul, kuid kui läbimine toimub indeksite kasutamisega (näiteks get(i) tsüklis), siis ArrayList on märkimisväärselt kiirem.

Näide:

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();
// listide täitmine

// Kiire läbimine ArrayListis
for (int i = 0; i < arrayList.size(); i++) {
    String item = arrayList.get(i); // O(1)
}

// Aeglane läbimine LinkedListis indeksite kasutamisel
for (int i = 0; i < linkedList.size(); i++) {
    String item = linkedList.get(i); // O(n)
}

// Soovitatav on kasutada iteratori või foreach LinkedListi jaoks
for (String item : linkedList) {
    // elemendi töötlemine
}

Seega on läbimine ArrayListis kiirem, eriti kui on vaja juurdepääsu indeksi järgi.