Связанные списки лучше, чем массивы для добавления / удаления элементов в любой позиции в списке?

Question

Меня учили, что в целом добавление и удаление из связанного списка имеет тенденцию быть лучше, поскольку память никогда не должна перемещаться для размещения новых элементов.Я не уверен, применимо ли это к тому, когда добавление / удаление может быть в любой позиции в списке.

Если я прав, связанный список будет работать следующим образом;Он найдет позицию узла, который должен быть добавлен / удален за O (n) время, затем добавит / удалит узел в O (1), давая общее время O (n).

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

. Отсюда, кажется, нет явного преимущества в обоих случаях.Если посмотреть на средний случай, связанный список будет в среднем выполнять n / 2 операций в среднем, так как узел будет в среднем находиться в середине списка.

Что касается массива, удаление также потребуетусредните n / 2 операций по аналогичным причинам, в то время как при добавлении потребуется n операций, если необходимо переместить все данные для размещения дополнительного элемента, или n / 2, если места достаточно и необходимо переместить данные на 1 пространство.Даст ли это в среднем 2 * n / 3, и может ли это быть причиной того, почему связанный список будет лучше для этого?

Answer 1

добро пожаловать в ТАК!Интересный вопрос.
Я думаю, что вы правы, что обе операции выполняются за O (n) до тех пор, пока массив может быть расширен без выделения новой памяти.
Но если нужно было выделить новую память, вопрос в том, чтотогда произойдет.
В вашем вопросе вы предполагаете, что нужно было выделить память для нового полноразмерного массива.Но это может быть не так.
Я не эксперт по операционным системам, но я могу представить себе следующую ситуацию:
Память разделена на страницы.Если текущего nr страниц (n) недостаточно для хранения нового массива после вставки, для нового массива нужно n + 1 страниц.
В этом случае - если бы я был программистом операционных систем - я бы не сталвыделить новые n + 1 страницы и скопировать весь массив с помощью O (n) в новую память, но я бы выделил только еще одну страницу и настроил бы виртуальную память так, чтобы старые страницы и новые страницы были непрерывными в виртуальной памятидаже если они прерываются в физической памяти.В этом случае ситуация такая же, как если бы не было необходимости выделять новую память (с учетом записи O).
Чтобы сократить это, я полагаю, что обе реализации O (n).