插入双向链表中的任意位置

Question

我知道如何将一个项目附加到双向链接的哨兵列表中，并且在过去已经成功地实现了它。但是，我不确定如何在特定位置插入。例如，我有两个节点，想在它们之间插入一个值。由于链表中没有数字索引（我们使用链表的全部原因......），我该如何修复这段代码以便它可以在特定位置插入项目（这里的索引是一个描述性术语，不是数字索引):

def insert_element_at(self, val, index):
 new_node = Linked_List.__Node(val) 
 if index >= self.size or index < 0:
      raise IndexError
 elif self.size == 0:
     raise 'To add first value, please use append method.'
 else:
    self.current = self.header.next
    count = 0
    while count != index:
      self.current = self.current.next
      count += 1
    self.current.next = new_node
    new_node.next = self.current.next.next
    new_node.prev = self.current
    self.size += 1

在这种情况下，我使用 'count' 作为跟踪每次迭代位置的方法。这似乎不起作用，有没有人对我如何改进这段代码有任何想法？我认为我运行遇到的主要问题是当它遇到我的字符串方法时：

def __str__(self):  
  if self.size == 0:
    return '[ ]'
  self.current = self.header.next
  s = '[ '
  while self.current is not self.trailer:
    s += str(self.current.val)
    s += ', '
    self.current = self.current.next
  s += ' ]'
  return s

任何关于我如何改进它的想法或帮助都会很棒！

Answer 1

我认为问题在于将新节点链接到现有节点的操作顺序。当您执行 self.current.next = new_node 作为第一步时，您将无法访问 self.current.next 的原始值（它应该成为新节点之后的节点）。

这是我的做法：

while count != index:
  self.current = self.current.next
  count += 1
new_node.prev = self.current
new_node.next = self.current.next
self.current.next.prev = new_node
self.current.next = new_node

虽然我没有在上面这样做，但我也建议您将 current 设为局部变量而不是 self 的属性，因为函数中的局部变量访问起来更快比全局变量或属性。

插入双向链表中的任意位置

insert at arbitrary position in doubly linked sentinel list

python-3.x

doubly-linked-list