Python双向链表指定位置插入节点失效问题排查

原代码存在的核心问题 #

1. 参数传递错误：insert方法调用add_to_head(new_node)时，add_to_head接收的是值类型参数，会重新创建Node，导致传入的节点实例未被正确使用。
2. 插入逻辑缺失：找到目标位置节点后，仅设置了该节点的前驱为新节点，未完成双向链表的双向关联：
   • 未将新节点的后继指向目标节点
   • 未将目标节点的原前驱的后继指向新节点
   • 未设置新节点的前驱指向目标节点的原前驱
3. 冗余遍历逻辑：insert方法中同时用for和while两次遍历链表，逻辑重复且混乱。

修正后的完整代码 #

class DoublyLinkedList:
    def __init__(self):
        self.head_node = None
        self.tail_node = None
    
    def insert(self, pos, new_value):
        new_node = Node(new_value)
        # 插入头部
        if pos == 0:
            self.add_to_head(new_value)
            return
        
        current_node = self.head_node
        counter = 0
        # 遍历到目标位置的前一个节点
        while current_node is not None and counter < pos - 1:
            current_node = current_node.get_next_node()
            counter += 1
        
        # 如果遍历到尾部，插入到末尾
        if current_node is None or current_node.get_next_node() is None:
            self.add_to_tail(new_value)
            return
        
        # 执行中间插入的双向关联
        next_node = current_node.get_next_node()
        # 当前节点的后继指向新节点
        current_node.set_next_node(new_node)
        # 新节点的前驱指向当前节点
        new_node.set_prev_node(current_node)
        # 新节点的后继指向原后继节点
        new_node.set_next_node(next_node)
        # 原后继节点的前驱指向新节点
        next_node.set_prev_node(new_node)

    def add_to_head(self, new_value):
        new_head = Node(new_value)
        current_head = self.head_node

        if current_head is not None:
            current_head.set_prev_node(new_head)
            new_head.set_next_node(current_head)

        self.head_node = new_head

        if self.tail_node is None:
            self.tail_node = new_head

    def add_to_tail(self, new_value):
        new_tail = Node(new_value)
        current_tail = self.tail_node

        if current_tail is not None:
            current_tail.set_next_node(new_tail)
            new_tail.set_prev_node(current_tail)

        self.tail_node = new_tail

        if self.head_node is None:
            self.head_node = new_tail

    def print(self):
        current_node = self.head_node
        while current_node is not None:
            print(f"{current_node.get_value()}", end=" ")
            current_node = current_node.get_next_node()
        print()

class Node:
    def __init__(self, value, next_node=None, prev_node=None):
        self.value = value
        self.next_node = next_node
        self.prev_node = prev_node
        
    def set_next_node(self, next_node):
        self.next_node = next_node
        
    def get_next_node(self):
        return self.next_node

    def set_prev_node(self, prev_node):
        self.prev_node = prev_node
        
    def get_prev_node(self):
        return self.prev_node
    
    def get_value(self):
        return self.value

# 测试代码
dll = DoublyLinkedList()
dll.add_to_head('a')
dll.add_to_tail('c')
dll.print()  # 输出: a c
dll.insert(1, 'b')
dll.print()  # 输出: a b c

关键修改说明 #

• 修正add_to_head的参数传递：insert中调用add_to_head时传入new_value，而非节点实例，匹配方法的参数要求。
• 优化遍历逻辑：只通过一次while循环找到目标位置的前一个节点，简化插入操作的定位。
• 完善双向关联：插入中间节点时，同时处理当前节点、新节点、原后继节点三者的双向指针，确保链表结构正确。

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