Когда вы достигнете add до конца ArrayList, он вырастет сам, чтобы иметь место для запаса.Таким образом, если у вас есть 10-элементный элемент ArrayList, добавление в конце приведет к тому, что он внутренне выделит место для двадцати элементов, скопируйте десять уже имеющихся, а затем добавьте один.Затем, когда вы добавляете еще один элемент в конце, он просто вставляет этот двенадцатый элемент в пространство, которое он уже создал.
Технически это не дает ему постоянное время вставки в конце, но оно дает ему амортизируется постоянная вставка времени.То есть, при большом количестве операций стоимость приближается к постоянному времени;каждый раз, когда он увеличивается, он удваивается, поэтому у вас будет все большее число «свободных» вставок постоянного времени, прежде чем вам придется снова увеличивать и копировать.
Когда вы вставляете в начало , он не может этого сделать и всегда должен копировать весь список в новое место (линейное время).
Удаление с конца всегда постоянное время, потому что вы просто переключаете последнюю ячейку сбудучи «заполненным» до «свободного пространства».Вам никогда не нужно копировать список.
Что касается вашего второго вопроса, LinkedList сохраняет указатель на конец списка, поэтому add и remove там просто используют этот указатель и таким образомпостоянное времяНет быстрых указателей на середину списка, поэтому доступ к произвольному элементу требует линейного обхода времени от начала до (потенциально) конца.