一个关于python链表删除方法的问题

Question

我跟踪了一本数据结构书，在那里，我们用它的方法实现了一个 LinkedList 类，我有一个关于删除方法的问题

    def deletion(self, index):
        current_node = self.first_node
        current_index = 0
        if index == 0:
            self.first_node = self.first_node.next_node
        else:
            while current_index < (index - 1):
                current_node = current_node.next_node
                current_index += 1
            current_node.next_node = current_node.next_node.next_node

特别是关于这条线

current_node.next_node = current_node.next_node.next_node

。也许我已经数不清了，但据我了解，如果我传入索引 3，在 while 循环结束时 current_node 应该位于索引 2，但在书中，要删除索引 3，我们调用

current_node.next_node

将我们带到第三个索引，然后将其连接到第四个索引，这不应该执行我们需要的任何操作，但它实际上有效。那么，我是不是数错了还是怎么的？

Answer 1

当你想从（单）链表中删除一个节点时，你需要变异前驱节点，这样它的下一个属性就不再引用要删除的节点，而是引用该节点的后继。

在

while

循环结束时，情况如下：

           index−1               index                 index+1

       current_node
          ↓
       ┌─────────────┐       ┌─────────────┐       ┌─────────────┐
       │ data: 10    │       │ data: 20    │       │ data: 30    │
...───►│ next_node: ────────►│ next_node: ────────►│ next_node: ───... 
       └─────────────┘       └─────────────┘       └─────────────┘

这三个节点中间的一个具有给定的索引，需要删除。为此，我们必须更改其前任节点（即左图所示的节点）的

next_node

属性，这就是为什么

current_node

需要引用 that 节点，而不是要删除的节点。

那么问题就变成了：它的

next_node

引用的新值应该是多少？它应该指向要删除的节点的后继，即右图所示的节点。

最后，我们如何获得后继节点的引用呢？通过遵循

next_node

引用，我们到达中间节点，当我们从

that

节点获得 next_node 引用时，我们到达后继节点。因此需要两个“步骤”才能到达那里。

这就是我们需要这样做的原因：

current_node.next_node = current_node.next_node.next_node

此分配的右侧是对后继节点的引用（注意两个步骤：首先我们到达中间节点，然后我们再跳一步到右侧节点）。作业导致这种情况：

           index−1               index                 index+1

       current_node
          ↓
       ┌─────────────┐       ┌─────────────┐       ┌─────────────┐
       │ data: 10    │       │ data: 20    │       │ data: 30    │
...───►│ next_node: ────┐    │ next_node: ────────►│ next_node: ───... 
       └─────────────┘  │    └─────────────┘   ┌──►└─────────────┘
                        └──────────────────────┘

一旦执行此分配（并且

current_node

引用的节点发生变异），将无法再到达要删除的节点：不再有对其的引用。这意味着垃圾收集器（在后台运行）现在可以自由地释放该对象占用的内存，因此我们确实实现了这种情况：

           index−1                                   index

       current_node
          ↓
       ┌─────────────┐                             ┌─────────────┐
       │ data: 10    │                             │ data: 30    │
...───►│ next_node: ──────────────────────────────►│ next_node: ───... 
       └─────────────┘                             └─────────────┘

我希望这能澄清这一点。