Removing a Node
Conceptually, removing a node works by first finding the node to remove, then linking the node immediately before it to the one after it. This is a little tricky though, because our nodes only store a reference to the next node in the list, not the previous. Later in this course, you’ll learn about a more advanced type of linked list that stores references to both the previous and next nodes. But for now, we’ll have to follow a procedure similar to the
.add_before() method, where we always hold a reference to the node we previously visited. The
.remove_node() method will take the node data to remove.
00:58 When we reassign the head to the next node in the list, the previous head is no longer referenced by any variables, so the garbage collector knows it can free it from memory. In other words, the node is removed.
If the node to be removed is somewhere in the middle, we need to first store a reference to the previous node, which starts off as the head. Then, we can say
for node in self, if this node’s
.data is the target data, set the previous node’s
.next attribute to the
.next attribute of the node we’re currently visiting. This line of code right here is what links the previous node to the next one, effectively removing the node we’re on. Just like before, we need to ensure we’re updating the previous node
each time through this loop. And if the node isn’t found, we raise an exception. Here, I’ve got a linked list containing the values
"e", in that order. I’ll try to remove
02:29 And that’s it for our custom implementation of a linked list. You learned how to implement all of the most common linked list operations in Python. If you feel comfortable with this and you want a new challenge, I’d encourage you to try one of these challenges.
Number one: create a method to retrieve an element from a specific position. This index should be passed in through a method call, or—if you want to get really fancy—you can index into the
LinkedList type directly with square bracket notation.
Number two: create a method to reverse the linked list. And number three: if you want a more object-oriented challenge, create a
Queue object inheriting from the
LinkedList type we created. Create
Become a Member to join the conversation.