Wat is beter om te gebruiken: ArrayList of…

ArrayList.

Bij het verwijderen van een element uit het midden van de lijst:

ArrayList: Vereist het verschuiven van alle volgende elementen, wat in het slechtste geval ($O(n)$) tijd kost, waarbij $n$ het aantal elementen is. Gemiddeld blijft de operatie $O(n)$, omdat slechts de helft van de elementen verschoven hoeft te worden. De daadwerkelijke prestaties zijn vaak beter door een betere gegevenslokalisatie.
LinkedList: Vereist iteratie door de elementen tot het gewenste knooppunt ($O(n)$ in het slechtste geval, als de iteratie vanaf het begin of het einde start). Na het vinden van het knooppunt, kost het verwijderen $O(1)$.

Hoewel het verwijderen van het knooppunt zelf in LinkedList sneller is, maakt het zoeken naar het knooppunt vóór het verwijderen de algemene operatie gemiddeld trager dan in 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; // Grootte van de lijst
        int removeIndex = size / 2; // Index om te verwijderen (midden)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Verwijderen uit het midden
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Tijd voor verwijderen uit 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); // Verwijderen uit het midden
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Tijd voor verwijderen uit LinkedList: " + durationLinkedList + " ns");
    }
}

Benchmarkresultaten tonen dat, voor het verwijderen van een element uit het midden, ArrayList over het algemeen sneller is, ondanks de theoretische complexiteit van verschuiving. Dit komt doordat zoeken op index in LinkedList ($O(n)$) langzamer is dan verschuiven in ArrayList.

// ArrayList - toegang op index O(1), verwijderen O(n) (verschuiving)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Verwijdert "B" - vereist verschuiven van "C"

// LinkedList - toegang op index O(n), verwijderen O(1) (na het vinden van het knooppunt)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Verwijdert "B" - eerst moet het knooppunt "B" gevonden worden (O(n)), daarna verwijderen (O(1))

Kort samengevat, voor de operatie van verwijderen uit het midden, als je de index weet, is ArrayList vaak de voorkeur vanwege snellere toegang op index, wat de kosten van verschuiving compenseert.

Wat is beter om te gebruiken: ArrayList of LinkedList, als ik een element uit het midden van de lijst wil verwijderen?