ArrayList vs LinkedList pri iterácii cez milión prvkov — čo je rýchlejšie?

Pri iterácii cez milión prvkov bude ArrayList zvyčajne rýchlejší než LinkedList.

Dôvodom je, že ArrayList ukladá prvky v jednom súvislom poli, čo zabezpečuje dobrú lokalitu dát a efektívny prístup podľa indexu. Iterácia prebieha sekvenčne cez pole, čo je priaznivé pre cache procesora.

Naopak, LinkedList je dvojzávitovo prepojený zoznam, kde každý prvok obsahuje odkazy na susedov. Pri iterácii sa tieto odkazy sledujú, čo vedie k častým prístupom do pamäti a zlej cache efektívnosti.

Príklad:

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// naplnenie zoznamov
for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// Iterácia cez ArrayList
for (Integer num : arrayList) {
    // spracovanie num
}

// Iterácia cez LinkedList
for (Integer num : linkedList) {
    // spracovanie num
}

V tomto príklade bude iterácia cez ArrayList rýchlejšia vďaka lepšej lokalite dát a nižším nákladom na prechody odkazmi.

Ak je prístup k prvkom náhodný, vyhráva tiež ArrayList, pretože prístup podľa indexu v LinkedList je O(n).