Wat is de complexiteit van het toevoegen van een…

De complexiteit van het toevoegen van een element aan ArrayList in het gemiddelde geval is O(1).

Dit wordt bereikt door gebruik te maken van een dynamische array, en toevoegen gebeurt aan het einde van de lijst.

// Toevoegen aan het einde van de lijst
List<String> list = new ArrayList<>();
list.add("element"); // O(1) in het gemiddelde geval

Echter, als de interne array van ArrayList vol is, is een resize-operatie nodig. Dit omvat het maken van een nieuwe, grotere array en het kopiëren van alle bestaande elementen naar de nieuwe array. De complexiteit van deze operatie is O(n), waarbij n de huidige grootte van de lijst is.

// Voorbeeld waar een resize kan plaatsvinden
List<Integer> numbers = new ArrayList<>(3); // Initiële capaciteit 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Hier kan een resize plaatsvinden - O(n)

Als een element niet aan het einde van de lijst wordt toegevoegd (methode add(int index, E element)), maar in het midden of aan het begin, moeten alle volgende elementen één positie naar rechts worden verschoven. De complexiteit van deze operatie is O(n), waarbij n het aantal te verschuiven elementen is.

// Toevoegen aan het begin van de lijst
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Toevoegen aan het begin - O(n)

De complexiteit van het toevoegen van een element aan ArrayList hangt dus af van de plaats van toevoegen en de noodzaak van resize:

Operatie toevoegen	Gemiddeld geval	Worst-case (bij resize of niet aan het einde toevoegen)
`add(E element)` (aan het einde)	O(1)	O(n)
`add(int index, E element)`	O(n)	O(n)

Wat is de complexiteit van het toevoegen van een element aan ArrayList?