Naudojant kolekcijas, kuriuose atvejais pereiti yra greičiau: ArrayList ar LinkedList?

Java kolekcijose ArrayList ir LinkedList elementų kartojimas skiriasi dėl jų vidinės struktūros.

• ArrayList yra pagrįstas masyvu, todėl prieiga prie elemento pagal indeksą vyksta O(1) laiku. Kartojimas naudojant for ciklą su indeksais yra labai greitas.
• LinkedList yra dvipusis susietas sąrašas, kur prieiga prie elemento pagal indeksą reikalauja pereiti per sąrašą nuo pradžios arba pabaigos, tai užtrunka O(n) laiko.

Todėl, pereinant per visus elementus naudojant iteratorių arba foreach, tai yra maždaug tas pats abiejose kolekcijose, tačiau jei pereinama naudojant indeksus (pvz., get(i) cikle), tada ArrayList bus žymiai greitesnis.

Pavyzdys:

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();
// sąrašų užpildymas

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

// Lėtas perejimas LinkedList naudojant indeksus
for (int i = 0; i < linkedList.size(); i++) {
    String item = linkedList.get(i); // O(n)
}

// Rekomenduojama naudoti iteratorių arba foreach LinkedList
for (String item : linkedList) {
    // elemento apdorojimas
}

Taip, pereinamasis procesas yra greitesnis ArrayList, ypač jei reikalingas prieigos pagal indeksą procesas.