Čo je lepšie použiť: ArrayList alebo LinkedList, ak…

ArrayList.

Pri odstraňovaní prvku zo stredu zoznamu:

ArrayList: Vyžaduje posun všetkých nasledujúcich prvkov, čo v najhoršom prípade (pri odstraňovaní prvého prvku) trvá čas $O(n)$, kde $n$ je počet prvkov. Priemerné však operácia zostáva $O(n)$, pretože je potrebné posunúť len polovicu prvkov. Skutočný výkon je často lepší vďaka lepšej lokalite dát.
LinkedList: Vyžaduje iteráciu cez prvky, kým sa nenájde požadovaný uzol ($O(n)$ v najhoršom prípade, ak začína od začiatku alebo konca). Po nájdení uzla je odstraňovanie $O(1)$.

Hoci samotné odstraňovanie uzla v LinkedList je rýchlejšie, hľadanie uzla pred odstránením robí celkovú operáciu priemerné pomalšou ako v ArrayList.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListRemovalComparison {

    public static void main(String[] args) {
        int size = 100000; // Veľkosť zoznamu
        int removeIndex = size / 2; // Index na odstránenie (stred)

        // ArrayList
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Odstránenie zo stredu
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Čas na odstránenie z ArrayList: " + durationArrayList + " ns");

        // LinkedList
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            linkedList.add(i);
        }

        long startTimeLinkedList = System.nanoTime();
        linkedList.remove(removeIndex); // Odstránenie zo stredu
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Čas na odstránenie z LinkedList: " + durationLinkedList + " ns");
    }
}

Výsledky ukazujú, že pri operácii odstraňovania zo stredu, ak poznáte index, je ArrayList často vhodnejšou voľbou kvôli rýchlejšej operácii prístupu podľa indexu, čo kompenzuje náklady na posun.

// ArrayList - prístup podľa indexu O(1), odstránenie O(n) (posun)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Odstránenie "B" - posunie "C"

// LinkedList - prístup podľa indexu O(n), odstránenie O(1) (po nájdení uzla)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Odstránenie "B" - najskôr je potrebné nájsť uzol "B" (O(n)), potom odstrániť (O(1))

Celkovo, pre operáciu odstraňovania zo stredu, ak poznáte index, je ArrayList často vhodnejšou voľbou kvôli rýchlejšej operácii prístupu podľa indexu, čo kompenzuje náklady na posun.

Čo je lepšie použiť: ArrayList alebo LinkedList, ak chcem odstrániť prvok zo stredu zoznamu?