Co jest lepsze do użycia: ArrayList czy LinkedList, jeśli chcę usunąć element z środka listy?

ArrayList.

Przy usuwaniu elementu z środka listy:

• ArrayList: Wymaga przesunięcia wszystkich kolejnych elementów, co w najgorszym przypadku (przy usuwaniu pierwszego elementu) zajmuje czas $O(n)$, gdzie $n$ to liczba elementów. Jednak średnio operacja ta pozostaje $O(n)$, ponieważ trzeba przesunąć tylko połowę elementów. Rzeczywista wydajność jest często lepsza dzięki lepszej lokalizacji danych.
• LinkedList: Wymaga iteracji po elementach do znalezienia żądanego węzła ($O(n)$ w najgorszym przypadku, jeśli iteracja zaczyna się od początku lub końca). Po znalezieniu węzła, usunięcie go zajmuje $O(1)$.

Chociaż usunięcie samego węzła w LinkedList jest szybsze, to wyszukanie węzła przed usunięciem sprawia, że operacja ta jest średnio wolniejsza niż w 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; // Rozmiar listy
        int removeIndex = size / 2; // Indeks do usunięcia (środek)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Usunięcie ze środka
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Czas usunięcia 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); // Usunięcie ze środka
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Czas usunięcia z LinkedList: " + durationLinkedList + " ns");
    }
}

Wyniki benchmarków pokazują, że do usuwania elementu z środka, ArrayList jest zazwyczaj szybszy, mimo teoretycznej złożoności przesunięcia. Wynika to z faktu, że wyszukiwanie elementu po indeksie w LinkedList ($O(n)$) jest wolniejsze niż przesunięcie w ArrayList.

// ArrayList - dostęp po indeksie O(1), usunięcie O(n) (przesunięcie)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Usunięcie "B" - wymaga przesunięcia "C"

// LinkedList - dostęp po indeksie O(n), usunięcie O(1) (po znalezieniu węzła)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Usunięcie "B" - najpierw trzeba znaleźć węzeł "B" (O(n)), potem usunąć (O(1))

Podsumowując, dla operacji usuwania z środka, jeśli znasz indeks, ArrayList jest często bardziej preferowany ze względu na szybszą operację dostępu po indeksie, co rekompensuje koszty przesunięcia.