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)。因为这不会在您的代码中发生，所以存在第二次添加 same 节点的风险（当 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，即使列表已经有节点。

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

doubly_linked list Insert after a certain node ends in loop python

python

python-2.7

data-structures

python-3.x

doubly-linked-list