Для кого операция добавления элемента в середину медленнее — для List или для LinkedList?

Question

[Илья Лещенко]

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

Answer 1

[Mercury13]

Если нужно искать точку, куда добавить (в LinkedList переместить итератор, в List переместить итератор ИЛИ отыскать индекс) — медленнее LinkedList из-за вопросов с кэшем.
Если точка уже имеется и она в середине — медленнее List, просто из-за асимптотической сложности.

Comments

[Илья Лещенко]

Можете, пожалуйста, рассказать про проблемы с кэшем или рассказать, что изучить по этой теме?

[Mercury13]

В кэш подтягиваются несколько ячеек памяти подряд. А LinkedList держит данные вразброс.

[Илья Лещенко]

Mercury13, спасибо

Answer 2

[Василий Банников]

Получается, что скорость равна?

Нет, не равна.
Как минимум из-за того что big O показывает только характеристику, с которой растёт время.

Операция записи считается без чтения - в случае Linked List это значит, что мы пытаемся вставить, уже имея ссылку на нужный узел - нам не нужно тратить время на его поиск.

Чисто в теории, вставить элемент в середину большого Linked List будет дешевле, чем в середину большого List, тк в первом случае нам нужно будет выделить лишь небольшой кусочек памяти и поправить пару ссылок.

Во втором - придётся в худшем случае выделить кусок памяти побольше, чтобы уместились все данные и перекопировать весь список.

Конкретные числа для конкретных случаев скажет только бенчмарк.

Answer 3

[#]

Проблема в том, что для LinkedList операция чтения O(n), вставки - O(1). Для List - операция чтения O(1), вставки - O(n). Получается, что скорость равна?

если n=1, умозрительно да...
.. ну а цена вопроса?... не? не слыхал?... я молчу по новые фишки распараллеливания... хотя и не знаю (пока) на сколько уместны...

Comments

[Илья Лещенко]

Слышал, конечно, но тут вопрос более про сами структуры данных. Не думаю, что вопрос этот настолько дотошен

[#]

Илья Лещенко, по идее LinkedList, но это зависит от реализации. дотнет опен соурс, можно почитать. и все равно - итог зависит от сценария применения и объёмов данных.
на малых данных (вспомните о кешах процессоров и сегментации адресации) возможно разницы не будет. если будет - не грех это проверить тестами.

[#]

Илья Лещенко, если теория - LinkedList ...
если практика - бенчмарки...
и цена - чтение ;)))

[EDIsaev]

разница будет в любом случае и в любом случае LinkedList будет шустрее, т.к. в нём O(n) про операции чтения, а в List O(n) про операции записи, которые всегда медленнее. И чем больше список и, в случае List, сами элементы, тем более заметна будет разница