Apathy666
@Apathy666

Односвязные списки. Удаление элемента?

Есть ли способ удалить элемент из односвязного списка за О(1)? При условии, что у нас есть указатель на удаляемый элемент.
За О(n) с поиском такое сделать не проблема, а как без него за О(1)?
  • Вопрос задан
  • 121 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Только если вам известен ПРЕДЫДУЩИЙ элемент. Иначе за честные О(1) вы из односвязного списка ничего не удалите.

Можно амортизационно удалить за О(1) просто пометив этот элемент удаленным. Но тогда все функции, которые проходятся по списку, должны такие помеченные элементы действительно удалять во время прохода.

Суммарное время работы алгоритма будет как если бы удаление было за О(1). Но некоторые отдельные операции могут быть сильно медленнее, чем при честной константе. Например, если вы кучу раз добавите элемент в начало списка и тут же удалите, то потом вывод списка будет медленным, несмотря на то, что список должен быть пустым.

Но на практике этот метод, наверно, не применяется. Потому что вы же где-то берете указатель на удаляемый элемент. Обычно можно вместе с ним получать и указатель на предыдущий. Или тупо использовать двусвязные списки.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Alexandroppolus
@Alexandroppolus
кодир
Если это не последний элемент, то присваиваем в него значение из следующего, потом удаляем следующий
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы