Почему вставка элементов занимает такое время?
Про список Просто автор хитренький и считает, что задача получения указателя на нужный элемент в списке - это отдельная задача поиска, которая как раз делается за O(n). Ну а со вставкой все просто - она действительно делается за O(1). Тот факт, что на практике зачастую вставка состоит из поиска и собственно вставки хитренький автор замел под ковер. Остерегайтесь хитреньких авторов!

Про массив Нетрудно догадаться™, что при вставке в массив на самое первое место, нужно сдвинуть весь хвост массива на один элемент (чтобы было место, куда вставлять). Вот это сдвигание, по самой пессимистичной (когда вставляем в самое начало) оценке и занимает O(n).
Потому что, чтоб вставить элемент в массив в произвольное место, надо все остальные элементы сдвинуть на одну позицию.
Для вставки в список вы должны передать операции ссылку на элемент перед которым (или после которого) должен быть вставлен новый элемент. Имея такую ссылку операция происходит за константное количество шагов.
Такая же ситуация и с операцией удаления произвольного элемента.