doubly_linked list在循环python中某个节点结束后插入

Question

尝试在Python中学习数据结构，实现双链表。当我试图在一个元素后面插入一个新元素时，它会以一个连续的循环结束。请试着解释我哪里出错了，为什么它会结束它的连续循环。

我在这里发布了我的全部代码，但问题在insertAt。请帮忙。

class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class Double_list:
def __init__(self):
self.head = None

def beginning(self, data):
node = Node(data)
if not self.head:
self.head = node
else:
temp = self.head
node.next = temp
temp.prev = node
def addelement(self, data):
node = Node(data)
if not self.head:
self.beginning(data)
return
temp = self.head
last = temp
while temp.next:
temp = temp.next
temp.next = node
node.prev = temp

def ending(self, data):
self.addelement(data)
def insertAt(self, data, after=None):
node = Node(data)
temp = self.head
while temp and after:           
import pdb; pdb.set_trace()
last = temp
temp = temp.next
if last.data == after:
last.next = node
node.prev = last
node.next = temp
temp.prev = node

def remove(self,data):
temp = self.head
while temp:
if temp.data == data:
break
last = temp
temp =temp.next
last.next = temp.next
temp.next.prev = last
def printll(self):
temp = self.head
while temp:
print (temp.data, end=" ")
temp = temp.next
obj = Double_list()
obj.beginning(1)
obj.addelement(2)
obj.ending(3)
obj.insertAt(data=4,after=1)
obj.remove(2)
obj.printll()

Answer 1

由于insertAt最多插入一个节点，因此应在添加循环后立即退出(break(。因为这不会在代码中发生，所以存在第二次添加同一节点的风险(当after第二次出现时(，这将导致不一致的链表。

该方法中的其他一些问题：

• 当temp恰好是None时，您应该保护您的算法不访问temp.prev
• while循环条件不应包含有关after的任何内容
• 该函数不使用before，因此它不应该是一个参数
• 如果在列表中找不到after值，则不应插入任何节点，因此最好只在找到after时创建节点

所以：

def insertAt(self, data, after=None): # No `before`
temp = self.head
while temp:  # No condition on `after`
last = temp
temp = temp.next
if last.data == after:
node = Node(data)  # <-- moved!
last.next = node
node.prev = last
node.next = temp
if temp:  # avoid error
temp.prev = node
break  # stop looking further

另一个备注：即使列表已经有节点，beginning方法也应该始终执行self.head = node。