CODEWITHSUNDEEP
pythonpython-3.xlinked-listdoubly-linked-listgarbage
David Glenn
David Glenn

Reputation: 43

Removing a Node from a doubly linked list while maintaining position

I'm familiar with the general way to remove a Node from a doubly linked list in Python like this:

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

I have a Node called "current" somewhere in the middle of a linked list. My goal is to remove the Node and have the new "current" become the Node after it. I've written code that accomplishes this, but it leaves some useless references lying around.

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

From here, the list is in the correct order and no references point to the removed Node, but the removed Node still has its .next and .prev references pointing back to the list. That seems like bad code to me, but since I don't have any references to the removed Node, I don't know how to access it to remove them.

Are these references even a problem? If so, what's the solution?

Upvotes: 1

Views: 701

Answers (1)

Terry Jan Reedy
Terry Jan Reedy

Reputation: 19184

If the Node being removed is immediately garbage-collected, then its dead links go away and cannot cause problems. If there are no other references to it, but it is kept around (as in interpreters other than CPython), then its dead references will keep .prev and .next alive and not gc'ed, even when they might be. If there are other references to the Node, then its incorrect references might be a problem.

To me, the cleanest procedure would be to follow each link just once and augment your code as follows.

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

Lines 5 and 6 can be removed if you know that line 7 causes the previous current node to be gc'ed.

Upvotes: 1

Related Questions