Масъулияти илова кардани унсур ба ArrayList чӣ қадар аст?

Суръати илова кардани ун element ба 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)