ArrayList-ə element əlavə etməyin mürəkkəbliyi nədir?

ArrayList-ə element əlavə etmənin orta hesabla mürəkkəbliyi O(1)-dir.

Bu, dinamik massivdən istifadə etməklə həyata keçirilir və əlavə etmə siyahının sonuna edilir.

// Siyahının sonuna əlavə
List<String> list = new ArrayList<>();
list.add("element"); // Orta hesabla O(1)

Ancaq, əgər ArrayList-in daxili massivi doludursa, onun ölçüsünü artırmaq (resize) əməliyyatı tələb olunur. Bu, yeni, daha böyük massiv yaratmaq və bütün mövcud elementləri yeni massivə köçürməkdən ibarətdir. Bu əməliyyatın mürəkkəbliyi O(n)-dir, burada n siyahının hazırkı ölçüsüdür.

// Resize ola biləcək nümunə
List<Integer> numbers = new ArrayList<>(3); // Başlanğıc tutumu 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Burada resize ola bilər - O(n)

Əgər element siyahının sonuna deyil, ortasına və ya əvvəlinə əlavə olunursa (metod add(int index, E element)), bütün sonrakı elementlərin sağa doğru hərəkət etdirilməsi lazımdır. Bu əməliyyatın mürəkkəbliyi O(n)-dir, burada n hərəkət etdiriləcək elementlərin sayıdır.

// Başlanğıca əlavə
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Başlanğıca əlavə - O(n)

Beləliklə, ArrayList-ə element əlavə etmənin mürəkkəbliyi əlavə olunma yerinə və resize ehtiyacına bağlıdır:

Əlavə əməliyyatı	Orta hesabla	Ən pis halda (resize və ya sona əlavə olunmursa)
add(E element) (sona)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)