Mekkora az összetettség egy elem hozzáadása az ArrayList-hez?

Az ArrayList-hez elem hozzáadásának átlagos összetettsége O(1).

Ez a dinamikus tömb használatával érhető el, és a hozzáadás a lista végén történik.

// Hozzáadás a lista végéhez
List<String> list = new ArrayList<>();
list.add("elem"); // Átlagosan O(1)

Azonban, ha az ArrayList belső tömbje megtelt, akkor növelni kell a méretet (resize). Ez magában foglalja egy új, nagyobb tömb létrehozását és az összes meglévő elem átmásolását az új tömbbe. Ennek az műveletnek a komplexitása O(n), ahol n a lista aktuális mérete.

// Példa, ahol resize történhet
List<Integer> numbers = new ArrayList<>(3); // Kezdeti kapacitás 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Itt történhet resize - O(n)

Ha az elem nem a lista végére kerül (metódus add(int index, E element)), hanem középre vagy a lista elejére, akkor minden következő elemet egy pozícióval jobbra kell tolni. Ennek az összetettsége O(n), ahol n a tolni kívánt elemek száma.

// Hozzáadás a lista elejére
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Hozzáadás a lista elejére - O(n)

Így az ArrayList-hez való elem hozzáadás összetettsége attól függ, hogy hol történik a hozzáadás, és szükség van-e resize-re:

Hozzáadási művelet	Átlagos eset	Legrosszabb eset (resize vagy nem a végére történő hozzáadás)
add(E element) (a végére)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)