单链表删除

Question

我在做单链表实现，我记得Linus Torvalds在这里谈到过。

在单链表中，为了删除节点，我们应该可以访问上一个节点，然后更改它当前指向的节点。

因此，无论如何，我们都应该可以访问上一个节点。

但是Linus Torvalds通过在C中使用地址的概念删除了这个特例。因此head也有“前面的东西”，即指向head的head的地址。因此，他使用了C的指针和地址特性来删除特殊情况。

我认为这种单链表中的特殊情况删除不能在python中完成，因为我们没有指针的概念（因此我将无法在头之前走一步）？我说得对吗？

Answer 1

阅读您的问题时，我的第一个想法是：为什么要用python构建一个单链接列表？Python提供了丰富的集合类型，您可以使用这些集合类型，而不必担心它们是作为单链表、双链表还是一些非递归数据结构（通常更容易处理）实现的。

但是你的问题的答案是：Python当然允许构建一个单链表。例如，以下代码就是这样做的：

class Node:
    def __init__(self, x, next):
        self.x = x
        self.next = next

    def __str__(self):
        return "<{}, {!s}>".format(self.x, self.next)

n = Node(1, None)
n = Node(2, n)
n = Node(3, n)
print(n)  # output: <3, <2, <1, None>>>

n.next.next = n.next.next.next
print(n)  # output: <3, <2, None>>

与C的区别在于：我们不必malloc（）或使用指针，因为python为我们处理内存。Python有引用而不是指针，它们很相似，但更安全，更易于使用。

然而，在实现链接列表之前，您应该考虑您的需求是关于集合的，并且您可以从内置的或集合模块中选择一个好的。

Answer 2

您不能在Python中使用Linus的特定技巧，因为众所周知，Python没有指针（本身）或运算符地址。但是，您仍然可以通过为列表提供一个虚拟头节点来消除列表头的特殊情况。您可以将此作为列表设计的固有部分来完成，也可以通过创建一个额外节点并使其将第一个数据承载节点引用为下一个节点来动态完成。无论哪种方式，您可能要删除的所有节点都是内部节点，而不是特殊情况。

Answer 3

当然，你可以在Python中做到这一点。他的意思是，你有一些代表列表本身并指向列表头部的数据结构，你可以像处理第一个列表项时一样操纵列表项中的指针。

现在Python不是C，所以实现可能会有所不同，但原则适用。列表本身与其第一个项不是同一个对象，列表项不应具有与整个列表相同的方法，因此为它们使用不同类型的对象是有意义的。

然而，它们都可以使用同名的属性（例如Next）来指向下一个项。因此，当您遍历列表时，您处于第一项，“上一个”项是列表本身，如果您需要删除第一项，您正在操作它的“下一个”属性。

当然，在现实世界中，除非作为练习，否则永远不会编写自己的Python链表类。内置的列表效率更高。