Kui keeruline on lisada element ArrayList-i?

Keskmiselt on ArrayList-i elemendi lisamise keerukus O(1).

See saavutatakse dünaamilise massiivi kasutamisega ning lisamine toimub nimekirja lõppu.

// Lisamine nimekirja lõppu
List<String> list = new ArrayList<>();
list.add("element"); // Keskmiselt O(1)

Kuid juhul, kui ArrayList-i sisemassiv on täis, on vaja selle suurust suurendada (resize). See hõlmab uue, suurema massiivi loomist ja kõigi olemasolevate elementide kopeerimist uude massiivi. Selle operatsiooni keerukus on O(n), kus n on nimekirja praegune suurus.

// Näide, kus võib toimuda resize
List<Integer> numbers = new ArrayList<>(3); // Algne maht 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Siin võib toimuda resize - O(n)

Kui element lisatakse mitte nimekirja lõppu (meetodiga add(int index, E element)), vaid keskele või algusesse, on vaja kõiki järgnevaid elemente ühe positsiooni paremale nihutada. Selle operatsiooni keerukus on O(n), kus n on nihutatavate elementide arv.

// Lisamine alguses
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Lisamine alguses - O(n)

Seega sõltub ArrayList-i elemendi lisamise keerukus lisamise kohast ja vajadusest teha resize:

Lisamise operatsioon	Keskmine juhtum	Halvim juhtum (resize või lisamine mitte lõppu)
add(E element) (lõppu)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)