Как будет вести себя связный список (LinkedList) и массивный список (ArrayList), если в них вставить элемент?

Вставка элемента в LinkedList требует обхода списка до нужной позиции, что занимает O(n) в худшем случае. Сама вставка элемента - O(1), так как нужно обновить всего два указателя (текущего и предыдущего элемента).

Вставка элемента в ArrayList в середину требует сдвига всех последующих элементов на одну позицию вправо, что занимает O(n). Вставка в конец списка блиска к O(1) в среднем случае, если есть свободное место. Если массив заполнен, происходит его пересоздание и копирование элементов (аммортизированно O(1)).