请求完善双向链表insert方法并讲解其实现逻辑

完整实现后的.insert()方法 #

def insert(self, pos, new_value):
    if pos == 0:
      self.add_to_head(new_value)
    else:
      current_node = self.head_node
      for i in range(pos):
        if current_node.get_next_node() is None:
          self.add_to_tail(new_value)
          return
        current_node = current_node.get_next_node()
      
      new_node = Node(new_value)

      # 补充的核心代码
      prev_node = current_node.get_prev_node()
      prev_node.set_next_node(new_node)
      new_node.set_prev_node(prev_node)
      new_node.set_next_node(current_node)
      current_node.set_prev_node(new_node)

方法逻辑详解 #

整体流程 #

• 当插入位置pos为0时，直接复用已实现的add_to_head()完成头部插入
• 当pos不为0时：
  1. 从链表头节点开始遍历pos步，定位到目标位置的current_node（新节点需要插入到该节点之前）
  2. 遍历中若发现当前节点的下一个节点为空，说明pos超出链表长度，直接调用add_to_tail()将新节点插入尾部
  3. 定位到合法位置后，创建新节点，通过调整双向指针完成插入操作

指针调整核心步骤 #

1. 获取前驱节点：prev_node = current_node.get_prev_node()
   • 找到current_node的前一个节点，这是插入操作的起始连接点
2. 正向连接前驱与新节点：prev_node.set_next_node(new_node)
   • 断开前驱节点原本指向current_node的正向链路，改为指向新节点
3. 反向连接新节点与前驱：new_node.set_prev_node(prev_node)
   • 建立新节点到前驱节点的反向指针，保证链表支持反向遍历
4. 正向连接新节点与目标节点：new_node.set_next_node(current_node)
   • 建立新节点到current_node的正向链路，维持链表连续性
5. 反向连接目标节点与新节点：current_node.set_prev_node(new_node)
   • 建立current_node到新节点的反向指针，完成双向链表的节点插入闭环

测试验证 #

运行题目提供的测试代码：

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

结果符合预期，插入后链表可正常正向遍历，且因双向指针设置正确，反向遍历也能正常工作（可自行添加反向打印方法验证）

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