Сколько дополнительной памяти выделяется при вызове LinkedList.add()?

При вызове LinkedList.add() выделяется дополнительная память под новый узел списка — объект Node. Это O(1) памяти на одно добавление: массив не пересоздаётся и существующие элементы не копируются.

Метод LinkedList.add() добавляет элемент в конец списка, увеличивая его размер на 1. Для этого создаётся новый внутренний узел списка, который хранит ссылку на добавляемый элемент, а также ссылки на соседние узлы. После создания узла обновляются ссылки prev и next, чтобы включить его в цепочку.

Важно различать память под сам переданный объект и память под узел списка. Если объект уже создан и передан в add(), то LinkedList не создаёт копию этого объекта, а сохраняет ссылку на него. Но новый Node всё равно создаётся, поэтому утверждение «дополнительная память не выделяется» некорректно.

В отличие от ArrayList, где при нехватке ёмкости может потребоваться создание нового массива и копирование элементов, LinkedList не пересоздаёт общий массив. Поэтому стоимость по дополнительной памяти на один вызов add() — постоянная, то есть O(1), но не нулевая.