Почему в LinkedList добавление элемента в начало и конец имеет константную сложность O(1)?

Для LinkedList сложность O(1) обеспечивается его структурой данных — двусвязным списком, где каждый узел хранит ссылки на предыдущий и следующий элементы, а сам список хранит ссылки на голову (first) и хвост (last).

Как это работает:

• Добавление в начало (addFirst(e)): Создается новый узел, который становится новой головой. Его ссылка next указывает на старую голову. Ссылка first списка обновляется. Операция выполняется за константное время.
• Добавление в конец (addLast(e)): Создается новый узел, который становится новым хвостом. Его ссылка prev указывает на старый хвост. Ссылка last списка обновляется. Операция также выполняется за O(1).

Пример кода:

LinkedList<String> list = new LinkedList<>();
list.addFirst("A"); // O(1) - добавляем в начало
list.addLast("Z");  // O(1) - добавляем в конец
// Состояние списка: ["A"] -> ... -> ["Z"]

Важное уточнение:

• ArrayList: Добавление в конец (add(e)) в среднем O(1) (амортизированно), но при переполнении внутреннего массива требует его увеличения и копирования (O(n)). Добавление в начало (add(0, e)) всегда O(n), так как требует сдвига всех существующих элементов.