Dlaczego operacja dodawania elementu do tablicy ArrayList może mieć złożoność i jakie cechy są przy tym brane pod uwagę?

Dodanie elementu do ArrayList zwykle odbywa się z amortyzowaną stałą złożonością O(1), ale czasami może być droższe ze względu na konieczność rozszerzenia wewnętrznej tablicy.

Cechy:

• ArrayList przechowuje elementy w tablicy o stałym rozmiarze.
• Przy dodawaniu nowego elementu, jeśli wewnętrzna tablica jest pełna, tworzy się nowa tablica większego rozmiaru (zwykle 1,5-2 razy większa), a wszystkie istniejące elementy są do niej kopiowane.
• Ta operacja kopiowania zajmuje O(n), gdzie n to aktualna liczba elementów.
• Jednak takie rozszerzenia nie zdarzają się przy każdym dodaniu, a rzadko, więc średnia (amortyzowana) złożoność dodawania pozostaje O(1).

W związku z tym, podczas dodawania, ważne jest, aby pamiętać, że w rzadkich przypadkach operacja może być kosztowna z powodu redystrybucji pamięci i kopiowania elementów.