Я где-то читал, что операции ArrayList add () и remove () выполняются в " амортизированное постоянное "время". Что именно это означает?
В реализации add (item) я вижу, что ArrayList использует буфер массива, который составляет не более 3/2 размера списка, и если он заполнен, вызывается System.arraycopy () , который должен выполняться за O (n), а не за O (1) раз. Значит ли это, что System.arraycopy пытается сделать что-то более умное, чем копирование элементов один за другим во вновь созданный массив, поскольку время на самом деле O (1)?
Заключение: add (item) выполняется в амортизированное постоянное время, но add (item, index) и remove (index) не работают, они выполняются в линейном времени (как объяснено в ответах).