>> даже если мы в C забьём на скорость, и будем использовать список, где придётся десятку указателей менять значения, обрабатывая при этом всякие специальные случаи.
> Зачем? Для обоих случаев в односвязном списке достаточно изменить ровно один указатель.
> И делается это вполне элегантно.Угу, менять надо один указатель и это можно сделать элегантно, но при выполнении ряда условий:
- список _односвязный_, а односвязные списки неудобны, потому что для удаления элемента надо либо иметь указатель на предыдущий элемент, либо перемещать содержимое следующего элемента в этот, что уже неэлегантно и не один указатель, да ещё и не работает с последним элементом
- удаляемый элемент выкидывается, и поэтому не требуется в нём менять значения указателей на что-нибудь типа NULL, во избежание возможных трудноотлавливаемых багов с "висячими" указателями
- список организован не "в лоб", а несколько хитрее, чтобы специальный случай удаления первого элемента не требовал бы специальных телодвижений -- например, это список с заголовком
Кстати я не уверен, что эти условия совместимы, что действительно можно придумать односвязный список (в котором достаточно поменять ровно один указатель), с которым не придётся обрабатывать краевых случаев. Двусвязный циклический с заголовком достаточно красивым получается, но там большинство операций -- это изменение четырёх указателей. Плюс подчастую приходится трогать три списочных ячейки, случайным образом разбросанные по памяти, а это потенциально три кеш-промаха.
> Опять таки скорость самого удаления в
> случае списков выше, а не ниже. У них проблема со скоростью
> на совсем других операциях, например на поиске элемента для удаления. Сдается
> мне, тебе стоит повторить теорию.
А что теория? Теория говорит о каких-то абстракциях, типа O(1) или O(n). То есть всё что она говорит, это то, что существует такое N, что при всех n>N удаление элемента из массива окажется медленнее, чем удаление из списка. И чё мне с того? При каком N такое случится? Теория отказывается отвечать на эти вопросы, а зря. Ведь если, допустим, это случается при N=10000, то подавляющее большинство моих контейнеров будет удалять элементы быстрее, если я буду использовать массивы, потому что я довольно редко использую массивы из десятков тысяч элементов и больше.
Списки -- это всегда кеш-промахи в промышленных количествах. А раз кеш-промахи, значит алгоритм в целом начинает упираться в скорость доступа к DRAM, а эта скорость никакая. Она десятилетиями наращивает отставание от скорости процессоров. И не видно признаков тому, что этот тренд сломается в обозримом будущем. Насколько я понимаю этот вопрос -- скорость доступа к памяти зависит от размера этой памяти (я подозреваю, что там логарифмическая зависимость), объёмы памяти постоянно наращиваются, и если мы не получаем замедления DRAM с годами, то лишь благодаря самоотверженному труду разработчиков микросхем памяти. Но если мы не получаем _абсолютного_ замедления, то _относительное_ (в сравнении с процессором) тем не менее имеет место.
Процессоры заточены на работу с массивами, а вот рандом-акцесс им даётся сложно, и при таких раскладах, теоретический O(1) может быть медленнее, чем практический O(n). А если мы ещё вспомним, что при удалении элемента из списка надо не забыть скормить освобождённую списочную ячейку в функцию free, то есть дёрнуть тормозную кучу и её структуры данных, то легко может выйти, что O(n) времени на memmove килобайта памяти, вызванный удалением элемента из массива, займёт меньше времени, чем O(1) на удаление элемента из списка.
