Сложность времени операции удаления связанного списка O (n) против O (1)

Question

Поскольку я рассматриваю большие обозначения O для структур данных и алгоритмов, я смущен, когда разные источники устанавливают временную сложность O (n) для удаления узла из связанного списка по сравнению с O (1). Например, большой O шпаргалка помещает O (1) при удалении узла, где, как я полагал, удаление узла будет O (n), потому что вы должны сначала найти узел, а затем удалить его.

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

Я рассмотрел следующие вопросы, но они не относятся к моему вопросу:

big O нотация для удаления элемента из связанного списка

Краткое описание для реализаций Java Collections Framework

Каковы временные сложности различных структур данных?

Answer 1

Согласно первому потоку , который вы просмотрели , временная сложность O (1) относится к удалению уже идентифицированного узла.

Если вы щелкнете ссылку «список односвязных» на просмотренной вами странице big-O, вы можете получить больше информации о задействованных функциях (включая код) - здесь . Это должно точно ответить на ваш вопрос:)

Answer 2

Ответ на ваш вопрос: да.

Как правило, когда указывается сложность времени O (1) для вставки или удаления в связанном списке, предполагается, что указатель на рассматриваемый узел уже известен. Это не совсем бесполезно, однако. Рассмотрим случай, когда вы хотите просмотреть список и удалить элементы, соответствующие определенному описанию. Со связанным списком это может быть сделано за O (n) время с O (1) дополнительным пространством. Для массива это обычно требует O (n ^ 2) времени или O (n) дополнительного пространства.