Python链表按索引插入节点异常：中间插入失效问题排查

问题描述 #

实现链表的头部、尾部及边界索引插入功能后，中间位置插入存在异常。向链表插入11、22、33后，尝试将77插入索引1（对应原节点22的位置），输出结果仍为11、22、33，预期输出应为11、77、22、33。

错误原因分析 #

insert方法的中间插入逻辑存在两处关键错误：

1. 未修改链表结构：找到目标位置的prev和curr节点后，仅创建新节点并赋值给局部变量curr，未将新节点接入链表（未更新prev._next指向新节点，也未让新节点的_next指向原curr），导致新节点完全游离于链表之外。
2. 循环条件错误：while count != i and curr._next is not None的条件会导致当插入位置为链表倒数第二个节点时，循环提前终止，无法定位到正确的插入位置；同时未更新链表的_count属性，链表长度始终不变。

修复后的完整代码 #

from copy import deepcopy

class _List_Node:
    def __init__(self, value, next_):
        self._value = deepcopy(value)
        self._next = next_

class List:
    def __init__(self):
        self._front = None
        self._rear = None
        self._count = 0

    def is_empty(self):
        return self._count == 0

    def printf(self):
        curr = self._front
        while curr is not None:
            print(curr._value)
            curr = curr._next

    def __len__(self):
        return self._count

    def prepend(self, value):
        Mnode = _List_Node(value, None)
        if self._front is None:
            self._front = Mnode
            self._rear = Mnode
            self._count += 1
        else:
            self._front = _List_Node(value, self._front)
            self._count += 1

    def append(self, value):
        Mnode = _List_Node(value, None)
        if self._front is None:
            self._front = Mnode
            self._rear = Mnode
            self._count += 1
        else:
            Enode = _List_Node(value, None)
            self._rear._next = Enode
            self._rear = Enode
            self._count += 1

    def insert(self, i, value):
        # 处理边界情况：索引超出范围则头部或尾部插入
        if i >= self._count:
            self.append(value)
        elif i <= 0:
            self.prepend(value)
        else:
            count = 0
            prev = None
            curr = self._front
            # 循环定位到目标索引的前一个节点
            while count < i:
                count += 1
                prev = curr
                curr = curr._next
            # 创建新节点，接入链表
            new_node = _List_Node(value, curr)
            prev._next = new_node
            self._count += 1

# 测试代码
LD = List()
LD.append(11)
LD.append(22)
LD.append(33)
LD.insert(1, 77)
LD.printf()

验证结果 #

运行上述代码后，输出结果为：

11
77
22
33

与预期一致，中间插入功能正常生效。

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