How to remove a node from a linked list in Python easily?

Question

I'm having a difficult time trying to create a function in a queue class to remove a certain node with the argument being the value of the node.


class LinkedQ:

    def __init__(self):
        self._first = None
        self._last = None
    
    def enqueue(self,x):
        ny = Node(x)
        if self._first == None:
            self._first = ny
            self._last = ny
        else:
            self._last.next = ny
            self._last = ny


    def remove(self,x):
        current_node = self._first

        while x != current_node.data: #Node(x):
            last_node = current_node
            current_node = current_node.next
            if current_node == Node(x):
                last_node.next = current_node.next
                return


    def display(self):
        if self._first == None:
            return None
        else:
            elements = []
            current_node = self._first
            elements.append(current_node.data)
            while current_node.next != None:
                current_node = current_node.next
                elements.append(current_node.data)
            
            print(elements)


class Node:
   def __init__(self, x, next = None):
      self.data = x
      self.next = next



p = LinkedQ()

p.enqueue(1)
p.enqueue(2)
p.enqueue(3)
p.enqueue(4)
p.enqueue(5)

p.display()


p.remove(3)
p.display()

So it's the function def remove(self,x) that I can't seem to get working. As it is right now I don't get an error message, but the output, using the def display(self):, is still the same:

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

meaning that the selected node hasn't been removed. Could somebody please tell me what I'm doing wrong? And how can I try to solve it instead? As you can see, I'm trying to solve it by changing the pointer of the previous node to point at the node that is located after our current node, making it disappear when nothing is pointing at it. That's how we are required to solve it.

PS. There are other functions in the code, such as enqueue() and isEmpty() but those aren't relevant in this case, they work properly as of now.

Does your enqueue method create Node objects? Because currently you are enqueuing integers not Node objects. Also, it appears your remove method is not indented properly. — AlyT, Dec 15 '20 at 13:10
Seeing your enqueue method actually may be relevant. Does it specify a next arg when it creates the Node object? Or is next always being left to the default None value? — AlyT, Dec 15 '20 at 13:15
Hi, it is indented correctly, however I apparently messed it up when I copied & pasted it here. And yes, it does create Node objects as you can see here: https://imgur.com/vGt5mjs and in the code above that I also edited to include enqueue() — gojira, Dec 15 '20 at 13:16

score 2 · Answer 1 · answered Dec 15 '20 at 13:30

2

Others have already shown that the culprit was the line if current_node == Node(x):, which should be if current_node.data == x:, unless you want to define an __eq__ member function in Node

But IMHO it is not the only problem: a LinkedQ as pointers to the head and the tail of the list. If you remove the first or last element of the queue, you have to reset the corresponding pointer (or both is the list becomes empty).

answered Dec 15 '20 at 13:30

Serge Ballesta

143,923
11
122
252

Thank you for your help and further comment about my problem. I added an if-statement to make sure that the remove function works for a the first element in the list. I'll have to modify it to work for a given x that does not exist in the list as well. – gojira Dec 15 '20 at 13:51
My answer doesn't address this issue so definitely take a look into this too! – AlyT Dec 15 '20 at 14:06

score 1 · Answer 2 · answered Dec 15 '20 at 13:24

You have a bug in your remove method :

def remove(self,x):
    current_node = self._first
    
    while current_node and x != current_node.data:
        last_node = current_node
        current_node = current_node.next
        if current_node.data == x: #<==== Here
            last_node.next = current_node.next
            return

AlyT · Accepted Answer · 2020-12-15T13:40:45.507

1

Your while loop breaks before it is able to remove the right value. If you put a print inside your while loop, to print the value of current_node.data, you'll see you only go into the loop for Node(1) and Node(2). After Node(2) the while loop condition breaks.

You should probably do something more like this:

while True:
    last_node = current_node
    current_node = current_node.next
    if current_node.data == x:
        last_node.next = current_node.next
        return

edited Dec 15 '20 at 13:40

answered Dec 15 '20 at 13:24

AlyT

261
1
10

Thank you so much for helping out! I understand the change you made, however I'm not entirely sure why `if current_node.data == x:` works but not `if current_node == Node(x)`, yours is comparing the values while mine is comparing the nodes. I assume you can't do that just like that? – gojira Dec 15 '20 at 13:55
1

Node(x) creates a new Node object. They have different memory addresses. Test this by using `x = Node(1); y = Node(1); print(id(x)); print(id(y)); print(x == y)`. You'll see that they are not the same memory address so the equality operator doesn't work. If you wanted the equality operator to work, you'd have to define an __eq__ method! – AlyT Dec 15 '20 at 13:59
1

Here's a good explanation of implementing object equality: https://stackoverflow.com/questions/1227121/compare-object-instances-for-equality-by-their-attributes – AlyT Dec 15 '20 at 14:01

How to remove a node from a linked list in Python easily?

3 Answers3