主页 / coding / 问题 / 77772794
Accepted
TEOTU
Asked: 2024-01-07 18:57:05 +0800 CST

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

  • 772

我跟踪了一本数据结构书，在那里，我们用它的方法实现了一个 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将我们带到第三个索引，然后将其连接到第四个索引，这不应该执行我们需要的任何操作，但它实际上有效。那么，我喜欢，数错还是什么？

python

1 个回答

  1. Best Answer

    当要从（单）链表中删除节点时，需要对前驱节点进行变异，使其 next 属性不再引用要删除的节点，而是引用该节点的后继节点。

    循环结束时while，情况如下图所示：

    
           index−1               index                 index+1

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

    这三个节点中的中间一个具有给定的索引，需要删除。为此，我们必须更改next_node其前任节点（即左图所示的节点）的属性，这就是为什么current_node需要引用该节点，而不是要删除的节点。

    那么问题就变成了：它的next_node参考值的新值应该是多少？它应该指向要删除的节点的后继节点，即右图所示的节点。

    最后，我们如何获得后继节点的引用呢？通过跟踪next_node引用，我们到达中间节点，当我们next_node从该节点获得引用时，我们到达后继节点。因此需要两个“步骤”才能到达那里。

    这就是为什么我们需要这样做：

    current_node.next_node = current_node.next_node.next_node

    该分配的右侧是对后继节点的引用（注意两个步骤：首先我们到达中间节点，然后我们再跳一步到右侧节点）。

    如果您愿意，您可以将该赋值分成多个语句，以便更好地阐明正在发生的情况：

    node_to_delete = current_node.next_node
node_after_deleted = node_to_delete.next_node
current_node.next_node = node_after_deleted

    分配导致这种情况：

    
           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: ───... 
       └─────────────┘                             └─────────────┘

    我希望这能澄清这一点。

    • 1

相关问题