რამდენად რთულია ელემენტის დამატება ArrayList-ში?

საშუალო შემთხვევაში ArrayList-ში ელემენტის დამატების სირთულე შეადგენს O(1)-ს.

ეს მიღწეულია დინამიური მასივის გამოყენებით, და დამატება ხდება სიის ბოლოში.

// სიის ბოლოში დამატება
List<String> list = new ArrayList<>();
list.add("element"); // საშუალო შემთხვევაში 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)

თუ ელემენტი ემატება სიის შუა ან დასაწყისში (metodით 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)