В учебнике CLRS «Введение в алгоритм» такой параграф есть на стр. 258.
Мы можем удалить элемент за O (1) раз, если списки имеют двойную связь. (Обратите внимание, что CHAINED-HASH-DELETE принимает в качестве входных данных элемент x, а не его ключ k, поэтому нам не нужно сначала искать x. Если хэш-таблица поддерживает удаление, то связанный список должен быть дважды связанными, чтобы мы могли быстро удалить элемент.Если бы списки были только односвязными, то для удаления элемента x нам сначала нужно было бы найти x в списке, чтобы мы могли обновить атрибут next предшественника x. В односвязных списках и удаление, и поиск будут иметь одинаковое асимптотическое время выполнения).
Что меня озадачивает, так это большие скобки, я не понял их логики. В двусвязном списке все равно нужно найти x, чтобы удалить его, чем он отличается от односвязного списка? Пожалуйста, помогите мне понять это!