如何在Python中轻松地从链接列表中删除节点

Question

我很难在队列类中创建一个函数来删除某个参数为节点值的节点。

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()

因此，函数def remove(self,x)似乎无法工作。现在我没有收到错误消息，但使用def display(self):的输出仍然相同：

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

这意味着所选节点尚未被移除有人能告诉我我做错了什么吗？我该如何解决它呢正如你所看到的，我正试图通过将上一个节点的指针改为指向当前节点之后的节点来解决这个问题，使其在没有任何东西指向它时消失。这就是我们需要解决的方法。

PS。代码中还有其他函数，如enqueue()和isEmpty()，但在本例中这些函数并不相关，它们目前可以正常工作。

Answer 1

其他人已经表明罪魁祸首是行if current_node == Node(x):，它应该是if current_node.data == x:，除非您想在Node中定义__eq__成员函数

但IMHO并不是唯一的问题：LinkedQ作为指向列表头部和尾部的指针。如果删除队列的第一个或最后一个元素，则必须重置相应的指针(或者两者都是列表变为空(。

Answer 2

while循环在能够移除正确值之前就中断了。如果你在while循环中放入一个print，以打印current_node.data的值，你会看到你只进入了node(1(和node(2(的循环。在节点(2(之后，while循环条件将中断。

你可能应该做一些更像这样的事情：

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

Answer 3

您的remove方法中有一个错误：

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