ArrayListке элемент кошуу канча татаалдыкка ээ?

ArrayListке элемент кошуу орточо учурда O(1) болуп саналат.

Бул динамикалык массивди колдонуу менен жетишилет жана кошуу тизмектин акырында болот.

// Тизмектин акырында кошуу
List<String> list = new ArrayList<>();
list.add("элемент"); // Орточо учурда O(1)

Бирок, эгер ArrayListтин ички массиви толуп калса, анын өлчөмүн көбөйтүү (resize) операциясы талап кылынат. Бул жаңы, чоңураак массив түзүү жана бардык бар элементтерди жаңы массивге көчүрүү менен ишке ашат. Бул операциянын татаалдыгы O(n), анда n — тизмектин учурдагы өлчөмү.

// Resize болушу мүмкүн болгон мисал
List<Integer> numbers = new ArrayList<>(3); // Баштапкы сыйымдуулук 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Мында resize болушу мүмкүн - O(n)

Эгер элемент тизмектин акырында эмес, ортосунда же башында кошулса (метод add(int index, E element)), бардык кийинки элементтер бир орун оңго жылышы керек. Бул операциянын татаалдыгы O(n), анда n — жылдырылчу элементтердин саны.

// Башында кошуу
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Башында кошуу - O(n)

Ошентип, ArrayListке элемент кошуу татаалдыгы кошуу ордуна жана resize талап кылынганына жараша болот:

Кошуу операциясы	Орточо учур	Эң жаман учур (resize же акыркы эмес кошуу)
add(E element) (акырында)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)