Cosa è meglio usare: ArrayList o LinkedList, se voglio eliminare un elemento dalla metà della lista?

ArrayList.

Quando si rimuove un elemento dalla metà della lista:

• ArrayList: Richiede lo spostamento di tutti gli elementi successivi, il che nel caso peggiore (rimozione del primo elemento) richiede tempo $O(n)$, dove $n$ è il numero di elementi. Tuttavia, in media, l’operazione rimane $O(n)$, poiché è necessario spostare solo la metà degli elementi. La performance reale è spesso migliore grazie a una migliore località dei dati.
• LinkedList: Richiede di iterare sugli elementi fino a trovare il nodo desiderato ($O(n)$ nel caso peggiore, se l’iterazione inizia dall’inizio o dalla fine). Dopo aver trovato il nodo, la rimozione richiede $O(1)$.

Sebbene la rimozione del nodo in sé in LinkedList sia più veloce, la ricerca del nodo prima di rimuoverlo rende l’operazione complessiva in media più lenta rispetto a 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; // Dimensione della lista
        int removeIndex = size / 2; // Indice per rimuovere (metà)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Rimozione dalla metà
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Tempo di rimozione di 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); // Rimozione dalla metà
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Tempo di rimozione di LinkedList: " + durationLinkedList + " ns");
    }
}

I risultati del benchmark mostrano che, per rimuovere un elemento dalla metà, ArrayList è generalmente più veloce, nonostante la complessità teorica dello spostamento. Ciò è dovuto al fatto che la ricerca per indice in LinkedList ($O(n)$) è più lenta rispetto allo spostamento in ArrayList.

// ArrayList - accesso per indice O(1), rimozione O(n) (spostamento)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Rimuove "B" - richiede lo spostamento di "C"

// LinkedList - accesso per indice O(n), rimozione O(1) (dopo aver trovato il nodo)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Rimuove "B" - prima bisogna trovare il nodo "B" (O(n)), poi rimuoverlo (O(1))

In sintesi, per l’operazione di rimozione dalla metà, se si conosce l’indice, ArrayList è spesso la scelta preferita grazie alla più rapida operazione di accesso per indice, che compensa i costi dello spostamento.