ArrayList ga element qo'shishning murakkabligi qanday?

ArrayList ga element qo'shish murakkabligi o'rtacha holatda O(1)dir.

Bu dinamik massivdan foydalanish bilan amalga oshiriladi va qo'shish ro'yxat oxirida amalga oshiriladi.

// Ro'yxat oxiriga qo'shish
List<String> list = new ArrayList<>();
list.add("element"); // O(1) o'rtacha holatda

Ammo, agar ArrayList'ning ichki massivi to'ldirilgan bo'lsa, uning o'lchamini oshirish (resize) operatsiyasi talab qilinadi. Bu yangi, kattaroq massiv yaratish va mavjud barcha elementlarni yangi massivga ko'chirishni o'z ichiga oladi. Bu operatsiyaning murakkabligi O(n), bu yerda n - ro'yxatning hozirgi o'lchami.

// Resize bo'lishi mumkin bo'lgan misol
List<Integer> numbers = new ArrayList<>(3); // Dastlabki sig'imi 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Bu yerda resize bo'lishi mumkin - O(n)

Agar element ro'yxatning o'rtasiga yoki boshiga qo'shilsa (metod add(int index, E element)), keyingi barcha elementlar o'ngga siljishi kerak. Bu operatsiyaning murakkabligi O(n), bu yerda n - siljishi kerak bo'lgan elementlar soni.

// Boshiga qo'shish
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Boshiga qo'shish - O(n)

Shu bilan, ArrayList'ga element qo'shish murakkabligi qo'shish joyiga va resize qilish zaruriyatiga bog'liq:

Qo'shish operatsiyasi	O'rtacha holat	Eng yomon holat (resize yoki oxiriga qo'shmaslik)
add(E element) (oxiriga)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)