Ποια είναι η πολυπλοκότητα προσθήκης ενός στοιχείου σε 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)

Αν το στοιχείο προστίθεται όχι στο τέλος της λίστας (μέθοδος 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)