Removing a single head/tail node in Doubly Linked Lists

Language Help Python
1 
def remove_head(self):

    removed_head = self.head_node

    if removed_head == None:

      return None

    self.head_node = removed_head.get_next_node()

    if self.head_node != None:

      self.head_node.set_prev_node(None)

    if removed_head == self.tail_node:

      self.remove_tail()

    return removed_head.get_value()

def remove_tail(self):

  removed_tail = self.tail_node

  if removed_tail == None:

    return None

  self.tail_node = removed_tail.get_prev_node()

  if self.tail_node != None:

    self.tail_node.set_next_node(None)

  if removed_tail == self.head_node:

    self.remove_head()

  return removed_tail.get_value()

In the code given here on removing a head/tail from a doubly linked list, I’m puzzled at this one line of code. There’s a line where we check if the head node is also the tail node (Which implies that there is only one node in the list). We use the .remove_tail() method if the head is also the tail. Similarly, we use the .remove_head() method if the tail is also the head. Won’t the two functions call each other indefinitely? Why are we using a method here?

2

Please edit your reply, or add new reply with formatted code as that’s a little difficult to read at present :laughing:, see How do I format code in my posts? for details.

3

Can you please check now?

4

Perhaps you could follow through with pen and paper what actually happens when there is a single Node in your list.

What happens when you call remove_tail() for this list?
What about calling .remove_head() for a different list with a single Node element?

Be careful here with comparisons using values that have potentially been changed- self.head_node and self.tail_node.

1 Like
5

I still don’t get it. If there is only one node in a doubly linked list, self.head_node and self.tail_node should be set to None. I don’t understand how the function goes. For example, if I run the .remove_head method on a single node, it should set the head_node instance variable to None as well as the tail_node instance variable to None. Can you explain how the function flows in the instance where we have only one node?

6

What you said makes sense. So the flow starts with the function you called (let’s say we called the .remove_head() method of your doubly linked list for now).

With a single node in the list self.head_node will be set to None in the .remove_head() function and there is only one element so removed_head == self.tail_node evaluates to True and we then call .remove_tail() too.

But .remove_tail would not call .remove_head() again, if you check the conditional before that function call can you see why?
if removed_tail == self.head_node:

Hint

What happened to self.head_node in the previous function?

2 Likes
7

Thank you so much sir! You’re a lifesaver! I totally get it now. I was hung up on this topic for so long. I feel relieved now. So, when we go through the .remove_tail() method, self.head_node would be None and ultimately the last conditional would evaluate to False and the function would return the value of the removed node.

1 Like
8

I still have just one more doubt. When removing the head of a doubly linked list with multiple nodes, we set the previous pointer of the new head to None and also set the head node of the list as the new head. But, the node which we’re trying to remove is still pointing to its next node (The new head). So, will that node still be present in the list or will it be cleared automatically by Python?

1 Like
9

To remove a node in a singly linked list you change the pointer of the node before it to the node after, the removed node still points at the node after but there’s no way to access that node. I believe python cleans up such nodes.

1 Like
10

As far as your doubly linked is concerned that object is gone anyway (there are no references to that object itself within the list so you cannot access it through that list). In your overall Python process this will likely result in the removal of that node as it’s probably caught by the standard reference counter.

This is quite a simple method, basically if you remove every reference to an object (such that it’s reference count reaches zero) then Python will schedule that object for removal. The fact that it contains references to other objects doesn’t matter, what matters is references to that object.

The proper garbage collection program is more complex than this as you frequently find situations like objects referring to each other (so their reference count is never zero) but with no external references. You may want to try searching the web for Python’s garbage collection if you wanted more information on this.

2 Likes