Удаление узла из двусвязного списка с сохранением позиции

Я знаком с общим способом удаления узла из двусвязного списка в Python следующим образом:

current.prev.next = current.next
current.next.prev = current.prev
current.next = None
current.prev = None

У меня есть узел под названием «текущий» где-то в середине связанного списка. Моя цель — удалить узел и сделать так, чтобы новый «текущий» стал узлом после него. Я написал код, который выполняет это, но он оставляет несколько бесполезных ссылок.

current = current.next
current.prev.prev.next = current   
current.prev = current.prev.prev

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

Являются ли эти ссылки вообще проблемой? Если да, то какое решение?


python-3.x python garbage linked-list doubly-linked-list
person David Glenn    schedule 19.02.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Если удаляемый узел сразу подвергается сборке мусора, то его неработающие ссылки исчезают и не могут вызвать проблем. Если на него нет других ссылок, но он сохраняется (как в интерпретаторах, отличных от CPython), то его мертвые ссылки сохранят .prev и .next живыми, а не сборщиком мусора, даже если они могут быть. Если есть другие ссылки на узел, то его неправильные ссылки могут быть проблемой.

Для меня самой чистой процедурой было бы перейти по каждой ссылке только один раз и дополнить свой код следующим образом.

next = current.next
prev = current.prev
prev.next = next
next.prev = prev
current.next = None
current.prev = None
current = next

Строки 5 и 6 можно удалить, если вы знаете, что строка 7 приводит к сбору мусора предыдущего текущего узла.

person Terry Jan Reedy    schedule 20.02.2015