在链表中的给定节点后插入到

Question

我在调试以下错误时遇到问题。我有一个链表，我试图在头和尾之间的某个位置插入一个值。但是我在从Node类调用new_node值时遇到了问题。这与我使用的python版本有关吗？

Traceback (most recent call last):
File "linked_list_add_after_given_node.py", line 47, in <module>
a.insert_after(2,42)
File "linked_list_add_after_given_node.py", line 34, in insert_after
new_node.next_node = prev_node.next_node
AttributeError: 'int' object has no attribute 'next_node'

这就是我的链接列表：

class Node:
def __init__(self, value=None, next_node=None):
self.value = value
self.next_node = next_node
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
def __len__(self):
return self.size

def push(self, new_value):
# 1 & 2: Init a node
#        insert data into node
new_node = Node(new_value)
# 3. make next of new node the head
new_node.next_node = self.head
# 4. Mode head to point to new node
self.head = new_node
self.size += 1
def insert_after(self, prev_node, new_value):
# 1. check if prev_node exists
if prev_node is None:
print("The given previous node must be in Linked List.")
return 
# 2. Create new node
# 3. insert value
new_node = Node(new_value)
# 4. Make next of new Node as next of previous node
new_node.next_node = prev_node.next_node
# 5. make next of prev_node as new node
prev_node.next_node = new_node
if __name__ == "__main__":
a = LinkedList()
a.push(1)
a.push(2)
a.push(100)
a.push(1000)
a.insert_after(2,42)
print(a.__len__())

Answer 1

您使用prev_node=2(一个'int'对象(调用LinkedList.insert_after()，但它要求prev_node具有属性'next_node'，例如Node对象。

您需要找到要插入的节点，并在调用insert_after时将其作为prev_node发送，或者您可以将insert_after修改为int，然后在链表中找到具有该值的第一个节点。

为此，我将在LinkedList中添加一个__iter__，将insert_after参数prev_node重命名为prev_value，然后在insert_after的顶部添加一个for循环，以找到要插入的节点并将其分配给prev_node。

Class LinkedList:
...
def __iter__(self):
curr = self.head
while curr:
yield curr
curr = curr.next_node
def insert_after(self, prev_value, new_value):
prev_node = None
for node in self:
if node.value == prev_value:
prev_node = node
break
# 1. check if prev_node exists
....