ArrayList'e öğe eklemenin karmaşıklığı nedir?

ArrayList'e öğe eklemenin ortalama karmaşıklığı O(1)dir.

Bu, dinamik bir dizi kullanılmasıyla sağlanır ve ekleme liste sonunda gerçekleşir.

// Listenin sonuna ekleme
List<String> list = new ArrayList<>();
list.add("element"); // Ortalama O(1)

Ancak, ArrayList'in iç dizisi doluysa, boyutunu artırma (resize) işlemi gerekir. Bu, yeni, daha büyük bir dizi oluşturmayı ve tüm mevcut öğeleri yeni diziye kopyalamayı içerir. Bu işlemin karmaşıklığı O(n)dir, burada n listenin şu anki boyutudur.

// Resize olabilecek bir örnek
List<Integer> numbers = new ArrayList<>(3); // Başlangıç kapasitesi 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Burada resize olabilir - O(n)

Eğer öğe listenin sonuna değil de ortasına veya başına ekleniyorsa, tüm sonraki öğelerin sağa kaydırılması gerekir. Bu işlemin karmaşıklığı O(n)dir, burada n kaydırılması gereken öğe sayısıdır.

// Listenin başına ekleme
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Başlangıca ekleme - O(n)

Dolayısıyla, ArrayList'e öğe ekleme karmaşıklığı, ekleme yerinin ve resize ihtiyacının olup olmamasına bağlıdır:

Ekleme işlemi	Ortalama durum	En kötü durum (resize sırasında veya sona eklenmiyorsa)
add(E element) (sona)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)