基于链表节点的Python优先队列insert方法异常排查

我用链表节点实现了Python优先队列，要求insert方法按从小到大的顺序插入元素。但执行以下插入操作时：

PQ = Priority_Queue()
PQ.insert(11)
PQ.insert(22)
PQ.insert(44)
PQ.insert(33)

输出结果为11,22,44，正确预期应为11,22,33,44。以下是我的实现代码：

from copy import deepcopy

class _PQ_Node:

    def __init__(self, value, _next):
        """
        -------------------------------------------------------
        Initializes a priority queue node that contains a copy of value
        and a link to the next node in the priority queue
        Use: node = _PQ_Node(value, _next)
        -------------------------------------------------------
        Parameters:
            value - value value for node (?)
            _next - another priority queue node (_PQ_Node)
        Returns:
            a new Priority_Queue object (_PQ_Node)
        -------------------------------------------------------
        """
        self._value = deepcopy(value)
        self._next = _next


class Priority_Queue:

    def __init__(self):
        """
        -------------------------------------------------------
        Initializes an empty priority queue.
        Use: pq = Priority_Queue()
        -------------------------------------------------------
        Returns:
            a new Priority_Queue object (Priority_Queue)
        -------------------------------------------------------
        """
        self._front = None
        self._rear = None
        self._count = 0

    def insert(self, value):
        """
        -------------------------------------------------------
        A copy of value is inserted into the priority queue.
        Values are stored in priority order. 
        Use: pq.insert(value)
        -------------------------------------------------------
        Parameters:
            value - a data element (?)
        Returns:
            None
        -------------------------------------------------------
        """

        # Your code here
        
        new_node = _PQ_Node(value,None)
        
        if self._count == 0:
            self._front = new_node
            self._rear = new_node
        else:
            current = self._front 
            #next = self._front._next
            while current is not None and current._value < value:
                current = current._next
            if current is not None and current._value > value:
                new_node._next = current
                current = new_node
                self._rear = new_node
                #holder = current
                #new_node._next = holder
                #self._rear = new_node
                print("Rear : ",self._rear._value)
                print("Current : ",current._value)
                
            else:
                self._rear._next = new_node
                self._rear = new_node
                

        self._count += 1
        return

错误根源 #

1. 未正确修改链表前驱节点指针 #

当插入元素到链表中间位置时（比如插入33到22和44之间），代码只修改了局部变量current指向新节点，但原链表中22的_next仍指向44，新节点完全没有被接入链表，导致元素丢失。

2. 错误更新队尾指针_rear #

只有当新节点插入到队尾时，才需要更新_rear。代码在插入中间位置时也修改了_rear，不仅破坏了队列结构，还导致后续操作逻辑混乱。

以插入33为例：

• 遍历后current指向44，进入中间插入分支
• 代码将new_node._next设为44，然后current = new_node——这只是改变了局部变量的指向，原链表的前驱节点（22）的_next并未指向新节点
• 同时错误地把_rear改为33，但此时33根本不在链表中

修复后的insert方法 #

def insert(self, value):
    """
    -------------------------------------------------------
    A copy of value is inserted into the priority queue.
    Values are stored in priority order. 
    Use: pq.insert(value)
    -------------------------------------------------------
    Parameters:
        value - a data element (?)
    Returns:
        None
    -------------------------------------------------------
    """
    new_node = _PQ_Node(value, None)

    if self._count == 0:
        self._front = new_node
        self._rear = new_node
    else:
        prev = None
        current = self._front
        # 遍历找到第一个大于value的节点位置
        while current is not None and current._value < value:
            prev = current
            current = current._next
        
        # 插入到队列头部
        if prev is None:
            new_node._next = self._front
            self._front = new_node
        # 插入到队列尾部
        elif current is None:
            self._rear._next = new_node
            self._rear = new_node
        # 插入到队列中间
        else:
            prev._next = new_node
            new_node._next = current
    
    self._count += 1

修复说明 #

• 新增prev变量跟踪当前节点的前驱，确保插入时能修改前驱的_next指针，将新节点正确接入链表
• 分三种场景处理插入：头部、尾部、中间，每种场景仅修改对应必要的指针
• 仅在插入尾部时更新_rear指针，避免错误修改队列尾节点的指向

修复后执行插入操作，队列输出将符合预期：11,22,33,44

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