用双列表实现链表添加头节点时触发索引越界错误，求排查

我用两个Python列表实现链表：values存节点值，pointers存指针（每个元素是对应节点指向的节点索引）。写了头插函数，逻辑是先把两个列表的元素后移，记录最后一个元素追加到末尾，再在索引0插入新节点，但运行时出现索引越界错误。

我的代码：

class LinkedList:
    def __init__(self):
        self.values = []
        self.pointers = []
        
    def addAtHead(self, val):
        if not self.values:
            self.values.append(val)         
            self.pointers.append(None)      
            return
        
        append_val = self.values[-1]
        
        for i in range(1, len(self.values)):
            self.values[len(self.values) - i] = self.values[len(self.values) - i-1]
            self.pointers[len(self.values) - i] = self.pointers[len(self.values) - i-1]
    
    
        self.values[0] = val
        self.pointers[0] = self.values[1]
    
        self.values.append(append_val)
        self.pointers.append(None)
        

ll = LinkedList()
ll.addAtHead(10)
ll.addAtHead(20)

错误信息：

Traceback (most recent call last):
  File "/main.py", line 29, in <module>
    ll.addAtHead(2)
  File "/main.py", line 20, in addAtHead
    self.pointers[0] = self.values[1]
                       ~~~~~~~~~~~^^^
IndexError: list index out of range

错误原因 #

1. 循环执行条件问题：当原链表只有1个节点时，len(self.values)等于1，range(1, len(self.values))等价于range(1,1)，循环体完全不执行。此时self.values的长度还是1，访问self.values[1]自然会触发索引越界。
2. 元素移动逻辑错误：你试图通过覆盖原列表元素实现“后移”，但没有先扩容列表。原列表长度不变的情况下，覆盖操作只会替换原有元素，不会腾出位置，后续访问超出原长度的索引必然出错。最后追加原最后一个元素的操作虽然会增加列表长度，但此时前面的覆盖已经破坏了原数据结构。

修正方案 #

方案一：利用列表insert方法简化实现 #

直接用insert在头部插入新节点，同时更新原有节点的指针（因为插入后所有原有节点的索引都+1，它们指向的节点索引也要同步+1）：

class LinkedList:
    def __init__(self):
        self.values = []
        self.pointers = []
        
    def addAtHead(self, val):
        if not self.values:
            self.values.append(val)
            self.pointers.append(None)
            return
        
        # 新节点插入头部，指针指向原来的头节点（现在位于索引1）
        self.values.insert(0, val)
        self.pointers.insert(0, 1)
        
        # 更新原有节点的指针：所有非None的索引值+1
        for i in range(1, len(self.pointers)):
            if self.pointers[i] is not None:
                self.pointers[i] += 1

# 测试验证
ll = LinkedList()
ll.addAtHead(10)
ll.addAtHead(20)
print(ll.values)    # 输出: [20, 10]
print(ll.pointers)  # 输出: [1, None]

方案二：修正原有的元素移动逻辑 #

先给列表扩容，再从后往前移动元素，确保每一步索引都有效：

class LinkedList:
    def __init__(self):
        self.values = []
        self.pointers = []
        
    def addAtHead(self, val):
        if not self.values:
            self.values.append(val)         
            self.pointers.append(None)      
            return
    
        # 先扩容列表，添加占位元素
        self.values.append(None)
        self.pointers.append(None)
        
        # 从最后一个原有元素开始往前遍历，将元素后移一位
        for i in range(len(self.values)-2, -1, -1):
            self.values[i+1] = self.values[i]
            self.pointers[i+1] = self.pointers[i]
            # 同步更新指针中的索引值
            if self.pointers[i+1] is not None:
                self.pointers[i+1] += 1
    
        # 在头部插入新节点，指针指向原头节点的新索引（1）
        self.values[0] = val
        self.pointers[0] = 1

# 测试验证
ll = LinkedList()
ll.addAtHead(10)
ll.addAtHead(20)
print(ll.values)    # 输出: [20, 10]
print(ll.pointers)  # 输出: [1, None]

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