Python循环链表头部插入时元素丢失问题修复求助

错误原因 #

• 核心问题：insert方法的条件分支为独立if判断，未用elif串联。当location=0执行完头部插入逻辑后，程序会继续判断location==-1不成立，进而进入else分支的中间插入逻辑，破坏已调整的链表结构，导致元素丢失。
• 次要问题：CSL_list的__init__方法重复定义self.head，未初始化self.tail，存在空指针隐患；display方法的循环终止条件错误，会遗漏最后一个节点的输出。

修复后代码 #

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

class CSL_list:
    def __init__(self):
        self.head = None
        self.tail = None

    def __iter__(self):
        node = self.head
        while node:
            yield node
            node = node.next
            if node == self.tail.next:
                break

    def display(self):
        if self.head is None:
            print("The list is empty")
        else:
            tempNode = self.head
            print("[ ", end="")
            while True:
                print(f"{tempNode.data} -> ", end="")
                if tempNode == self.tail:
                    break
                tempNode = tempNode.next
            print("]")

    def initialize(self,data):
        first_node = Node(data)
        first_node.next =  first_node
        self.head = first_node
        self.tail = first_node

    def insert(self,data,location):
        new_node = Node(data)
        if self.head == None:
            print("Linked List has not been initialized!")
        else:
            if location == 0:
                new_node.next = self.head
                self.head = new_node
                self.tail.next = self.head
            elif location == -1:
               new_node.next = self.tail.next
               self.tail.next = new_node
               self.tail = new_node
            else:
                index = 0
                tempNode = self.head
                # 可选添加边界校验：判断location是否超过链表长度
                while index < (location-1 ):
                    tempNode = tempNode.next
                    index += 1
                new_node.next = tempNode.next
                tempNode.next = new_node
            print("Inserted!")

if __name__ == '__main__':
    test_list = CSL_list()
    test_list.initialize(21)
    test_list.insert(20,-1)
    test_list.insert(22, -1)
    test_list.insert(23, -1)
    test_list.insert(24, -1)
    test_list.insert(989,2)
    test_list.insert(122,0)

    print([node.data for node in test_list]) 

运行结果 #

执行代码后输出为：

Inserted!
Inserted!
Inserted!
Inserted!
Inserted!
Inserted!
[122, 21, 20, 989, 22, 23, 24]

所有插入操作符合预期，头部插入后元素无丢失。

内容的提问来源于stack exchange，提问作者Sneiden