Removing a Node

Working With Linked Lists in Python Austin Cepalia 03:42

Transcript
Discussion (4)

00:00 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:43 Once again, we’ll throw an Exception if the list is empty. If the head node is the node to remove, we’ll simply change the head so that it points to the next node and stop execution there.

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.

01:13 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

01:50 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 "a", "b", "c", "d", and "e", in that order. I’ll try to remove "a".

02:13 That worked fine. Let’s try "d", a node in the middle.

02:20 Looks like that works too. Of course, if we try to remove a node that doesn’t exist, we’ll see an Exception.

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.

02:47 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.

03:03 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 .enqueue()

03:18 and .dequeue() methods that call upon the methods we created in this course to simulate queue behavior. With enough practice, you’ll be an expert at linked lists in no time.

03:31 The rest of this course will focus on more advanced types of linked lists: the doubly linked list and the circular linked list.

reebaabu on Dec. 31, 2020

Hi @Austin, can we reverse a linked list this way? Where my init function is:

    def __init__(self, nodes=None):
        self.head = None
        if nodes is not None:
            node = Node(data=nodes.pop(0))
            self.head = node
            for n in nodes:
                node.next = Node(data=n)
                node = node.next

    def reverse_list(self):
        if not self.head:
            raise Exception("List is empty")
        nodes_data = [node.data for node in self][::-1]
        self.__init__(nodes_data)
        return

Bartosz Zaczyński RP Team on Jan. 4, 2021

@reebaabu You’re not supposed to call the .__init__() method by hand on an already initialized instance. That would be frowned upon by experienced Python programmers. More importantly, however, it results in destroying all the previously existing nodes. So if someone still got their references, they would not be up-to-date anymore and would not update the current reversed list.

reebaabu on Jan. 4, 2021

@Bartosz, Thanks for the explanation.

paulfwatts on Dec. 26, 2022

It seems to me that the code does not handle the case where there is multiple copies of the same node data in the linked list, e.g. “b” is in the linked list twice.

Am I correct is this assumption ?

Become a Member to join the conversation.