Первое, что надо знать: LinkedList → это связанный лист. Он хранит все элементы по ссылкам. Сам лист всегда знает ссылку на свой первый элемент и на последний. И каждый элемент знает ссылку на предыдущий и на следующий. Меня очень путали картинки, где все элементы указывались подряд и кажется, что они хранятся рядышком в одном месте, но это не так. Картинка ниже, по моему мнению, лучше описывает реальное положение.
Все звездочки рандомно где-то разбросаны по небу. Первая звезда знает, где находится вторая, но ничего не знает про третью и четвертую. Вторая звезда знает, где лежит первая и где лежит третья, но понятия не имеет, где спряталась четвертая звездочка. И так далее. То есть это как цепочка из звеньев, где каждое звено знает о соседях, но понятия не имеет о более дальних звеньях.
Как происходит поиск по такому листу? К сожалению, тут придётся перебрать каждый элемент, переходя по ссылкам от 1 к 2, от 2 к 3, чтобы найти нужный индекс. Это долго. Поиск будет O(n). В ArrayList же все элементы лежат в одном месте, поэтому там поиск по индексу будет быстрым.
Предположим, нам надо найти 3-й элемент. Плюс LinkedList в том, что поиск начинается с той стороны, к которой элемент ближе. Очевидно, что третья звезда ближе к концу, поэтому в этом случае перебор начнётся с четвертой звёздочки.
Вставка в LinkedList происходит довольно быстро, но надо учитывать, что сначала нужный элемент надо найти перебором, поэтому тут тоже сложность O(n). Сначала находим, а потом просто вставляем и переписываем ближайшие ссылки. При удалении аналогично, но там элемент ещё какое-то время поваляется в памяти, занимая место. Вставить на первое место и на последнее будет О(1), потому что нам не надо искать эти элементы. Мы уже знаем изначально, где они находятся.
При вопросе про сложность, я отвечала так: будет O(1), если не учитывать время на поиск.
Заметьте, что стрелочки у 1 и 2 звезд не поменялись. И 4 и 5 тоже. У них изменился индекс, но сами звёзды остались на своём месте. Изменились только стрелочка у второй звезды и у четвертой. Только три звезды из всех приняли участие во вставке. Остальные ничего не знают и спокойно стоят на месте. Это вся разница. В ArrayList же при вставке пришлось бы сместить абсолютно все элементы, которые находят справа от нужного индекса.
Как выглядит удаление:
Мы просто удалили все стрелочки у желтой звезды и указали, что второй элемент ссылается на другую звезды. Все звезды остаются на своём месте и никуда не смещаются. Мы затронули только 3 элемента из шести.
Про ArrayList я рассказывала здесь: https://zen.yandex.ru/media/android_junior/arraylist-chto-mogut-sprosit-na-sobesedovanii-u-djuniora-5eb8517a0bd3a10518a550c3