Премахване на възел от двойно свързан списък при запазване на позиция

Запознат съм с общия начин за премахване на възел от двойно свързан списък в 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 живи и няма да бъдат gc'ed, дори когато може да са. Ако има други препратки към възела, тогава неговите неправилни препратки може да са проблем.

За мен най-чистата процедура би била да следвате всяка връзка само веднъж и да разширите кода си, както следва.

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

Редове 5 и 6 могат да бъдат премахнати, ако знаете, че ред 7 кара предишния текущ възел да бъде gc'ed.

person Terry Jan Reedy    schedule 20.02.2015