CODEWITHSUNDEEP
pythondoubly-linked-list
anon anon
anon anon

Reputation: 161

Doubly Linked list in python Using Del

I was analyzing a doubly linked list function that deletes a node. However Im a bit confused.

def remove( self, p ) :
        tmp = p.prev
        p.prev.next = p.next
        p.prev = tmp

Why is there a tmp = p.prev and p.prev = tmp. What is the purpose of those extra line? and finally, why is no nodes being deleted with "del"? shouldn't it be "del p" at the end of the code?

Thank you!

Upvotes: 0

Views: 222

Answers (1)

abarnert
abarnert

Reputation: 365975

First, if this is the entire function, it's wrong, which is probably part of the reason you're having trouble understand it.

To remove a node from a doubly linked list, you need to do three things:

  1. Make the previous node point ahead at the next node, instead of the p node.
  2. Make the next node point back at the previous node, instead of the current one.
  3. Delete the current node.

Because Python is garbage-collected,1 step 3 happens automatically.2

And step 1 is taken care of by p.prev.next = p.next.

But step 2 doesn't happen anywhere. p.next.prev is still pointing at p, instead of at p.prev. This means that if you walk the list forward, p won't be part of it—but if you walk backward, it will. So p isn't actually removed.

Meanwhile, tmp = p.prev followed by p.prev = tmp doesn't do anything useful.3 And, whatever it was trying to do, you almost never need tmp like that in Python; you can swap values with just x, y = y, x instead of tmp = x; x = y; y = tmp.

So, what you actually want here is:

def remove(self, p):
    p.prev.next = p.next
    p.next.prev = p.prev

1. CPython, the reference interpreter for Python that you're probably using, does garbage collection through automated reference counting, with a cycle breaker that runs occasionally. Whether this counts as "real" garbage collection or not is a nice holy-war argument, but it doesn't matter here.

2. You just need to drop all references to the object, and it becomes garbage and gets cleaned up automatically. So, you need to remove the references from the next and previous nodes to p, which you're already doing. And you need to let p go away, but you don't need del p for that—it's a local variable; it goes away when you return from the function. After that, it's up to the caller of remove; if they don't keep any references to the node, the node is garbage.

3. It could do something useful, if we temporarily assigned a different value to p.prev and wanted to restore it at the end of the function. But that isn't happening here, and I don't think whoever wrote this code intended anything like that; I think they were trying to do some kind of swap.

Upvotes: 3

Related Questions