Co je lepší použít: ArrayList nebo LinkedList, pokud…

ArrayList.

Při odstraňování prvku ze středu seznamu:

ArrayList: Vyžaduje posun všech následujících prvků, což v nejhorším případě (při odstraňování prvního prvku) trvá čas $O(n)$, kde $n$ je počet prvků. Průměrně však operace zůstává $O(n)$, protože je třeba posunout pouze polovinu prvků. Skutečný výkon je často lepší díky lepší lokalitě dat.
LinkedList: Vyžaduje iteraci přes prvky, dokud se nenajde požadovaný uzel ($O(n)$ v nejhorším případě, pokud začíná od začátku nebo konce). Po nalezení uzlu je odstraňování $O(1)$.

Ačkoliv je samotné odstraňování uzlu v LinkedList rychlejší, hledání uzlu před odstraněním činí celkovou operaci průměrně pomalejší než u 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; // Velikost seznamu
        int removeIndex = size / 2; // Index pro odstranění (střed)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Odstranění ze středu
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Čas odstranění 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); // Odstranění ze středu
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Čas odstranění z LinkedList: " + durationLinkedList + " ns");
    }
}

Výsledky ukazují, že pro odstranění prvku ze středu je ArrayList obvykle rychlejší, i přes teoretickou složitost přesunu. To je způsobeno tím, že hledání podle indexu v LinkedList ($O(n)$) je pomalejší než posun v ArrayList.

// ArrayList - přístup podle indexu O(1), odstranění O(n) (posun)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Odstranění "B" - posune "C"

// LinkedList - přístup podle indexu O(n), odstranění O(1) (po nalezení uzlu)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Odstranění "B" - nejdříve je třeba najít uzel "B" (O(n)), pak odstranit (O(1))

Celkově, pro operaci odstraňování ze středu, pokud znáte index, je ArrayList často vhodnější volbou díky rychlejší operaci přístupu podle indexu, což kompenzuje náklady na posun.

Co je lepší použít: ArrayList nebo LinkedList, pokud chci odstranit prvek uprostřed seznamu?