Was ist besser zu verwenden: ArrayList oder…

ArrayList.

Beim Entfernen eines Elements aus der Mitte der Liste:

ArrayList: Erfordert das Verschieben aller nachfolgenden Elemente, was im schlimmsten Fall (bei Entfernen des ersten Elements) $O(n)$ Zeit in Anspruch nimmt, wobei $n$ die Anzahl der Elemente ist. Im Durchschnitt bleibt die Operation jedoch $O(n)$, da nur die Hälfte der Elemente verschoben werden muss. Die tatsächliche Leistung ist oft besser aufgrund einer besseren Datenlokalität.
LinkedList: Erfordert eine Iteration durch die Elemente bis zum gewünschten Knoten ($O(n)$ im schlimmsten Fall, wenn die Iteration am Anfang oder Ende beginnt). Nach dem Finden des Knotens dauert das Entfernen $O(1)$.

Obwohl das Entfernen des Knotens in der LinkedList schneller ist, macht die Suche nach dem Knoten vor dem Entfernen die Gesamtoperation im Durchschnitt langsamer als bei 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; // Listengröße
        int removeIndex = size / 2; // Index zum Entfernen (Mitte)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Entfernen aus der Mitte
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Entfernung Zeit für 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); // Entfernen aus der Mitte
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Entfernung Zeit für LinkedList: " + durationLinkedList + " ns");
    }
}

Benchmark-Ergebnisse zeigen, dass für das Entfernen eines Elements aus der Mitte, ArrayList in der Regel schneller ist, trotz der theoretischen Komplexität des Verschiebens. Dies liegt daran, dass die Indexsuche in der LinkedList ($O(n)$) langsamer ist als das Verschieben in der ArrayList.

// ArrayList - Zugriff nach Index O(1), Entfernen O(n) (Verschiebung)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Entfernt "B" - erfordert das Verschieben von "C"

// LinkedList - Zugriff nach Index O(n), Entfernen O(1) (nach Finden des Knotens)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Entfernt "B" - zuerst muss der Knoten "B" gefunden werden (O(n)), dann entfernt werden (O(1))

Kurz gesagt, für die Operation des Entfernens aus der Mitte, wenn man den Index kennt, ist ArrayList oft die bevorzugte Wahl aufgrund der schnelleren Zugriffsoperationen nach Index, was die Kosten für das Verschieben ausgleicht.

Was ist besser zu verwenden: ArrayList oder LinkedList, wenn ich ein Element aus der Mitte der Liste entfernen möchte?