Какая сложность вставки в середину в LinkedList при заполненном массиве

Вставка в середину LinkedList имеет сложность O(n), так как требуется пройти от начала или конца до нужной позиции (в среднем n/2 операций). Однако сама вставка выполняется за O(1), так как достаточно изменить ссылки соседних узлов. Пример: ```java LinkedList list = new LinkedList<>(); list.add("A"); list.add("B"); list.add("D"); // Вставка "C" на позицию 2 list.add(2, "C"); // O(n) из-за поиска позиции ``` В отличие от ArrayList, где вставка в середину требует сдвига элементов (O(n)), LinkedList не требует перераспределения памяти. Однако частые вставки в середину всё равно неэффективны из-за необходимости поиска позиции.