在python末尾插入元素时的单链列表无限循环

Question

当我想在链表的末尾添加一个元素时，它会导致一个无限循环，下面是我使用的方法

#insert at the end of the list
def append(self, data=None):
new_node = Node(data)
if self.head is None:
self.head = new_node
itr = self.head
while itr.next:
itr.next = new_node
itr = itr.next

Answer 1

如果列表为空，则在头部添加新节点后，代码应该返回。

在那之后，你的while循环是一个无限循环

你需要在添加到它之前更新它的位置，然后在循环之外添加到它

def append(self, data=None):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
itr = self.head
while itr.next:
itr = itr.next
itr.next = new_node

另外，你的Node((应该有一个下一个的参数

Answer 2

您的问题在循环中：

while itr.next:
itr.next = new_node
itr = itr.next

当将项目附加到空列表时，itr最初等于new_node。您将itr.next设置为new_node，因此现在new_node.next等于new_node。您现在已经在列表中创建了一个循环，因此它将永远循环。

当把一个项目附加到列表中时，你应该只修改最后一个元素——循环只用于遍历列表直到最后。它应该看起来像：

def append(self, data=None):
new_node = Node(data)
if self.head is None:
self.head = new_node
else: 
# you only need to traverse the list when it isn't empty
itr = self.head
while itr.next:
itr = itr.next
itr.next = new_node # only add the new node after traversing the list

也就是说，这种追加方法的复杂性是O(n)，你可以通过保持一个指向列表尾部的指针并修改尾部来使其成为O(1)，而无需遍历列表来找到它