Nice! Now we have a bunch of helpful LinkedList methods under our belt.
The final use case we mentioned was the ability to remove an arbitrary node with a particular value. This is slightly more complex, since a couple of special cases need to be handled.
Consider the following list:
If node b is removed from the list, the new list should be:
We need to update the link within the a node to match what b was pointing to prior to removing it from the linked list.
Lucky for us, in Python, nodes which are not referenced will be removed for us automatically. If we take care of the references, b will be “removed” for us in a process called Garbage Collection.
For the purposes of this lesson, we’ll create a function that removes the first node that contains a particular value. However, you could also build this function to remove nodes by index or remove all nodes that contain a particular value.
Instructions
At the bottom of script.py, add a .remove_node() method to LinkedList. It should take value_to_remove as a parameter. We’ll be looking for a node with this value to remove.
In the body of .remove_node(), set a new variable current_node equal to the head_node of the list.
We’ll use current_node to keep track of the node we are currently looking at as we traverse the list.
Still inside the method body, use an if statement to check whether the list’s head_node has a value that is the same as value_to_remove.
If it does, we’ve found the node we’re looking for and we need to adjust the list’s pointer to head_node.
Inside the if clause, set self.head_node equal to the second node in the linked list.
Add an else clause. Within the else clause:
Traverse the list until
current_node.get_next_node().get_value()is thevalue_to_remove.(Just like with
stringify_listyou can traverse the list using awhileloop that checks whethercurrent_nodeexists.)When
value_to_removeis found, adjust the links in the list so thatcurrent_nodeis linked tonext_node.get_next_node().After you remove the node with a value of
value_to_remove, make sure to setcurrent_nodetoNoneso that you exit the loop.