单链表删除

Question

我在做单链表实现，我记得Linus Torvalds在谈论它here。

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

像这样

等任何一种方式，我们应该有机会获得一个节点。

但Linus Torvalds通过使用C中的地址的想法删除了特殊情况。因此，头部还具有'先前的事物'，它是指向头部的头部的地址。所以他使用了C的指针和地址特征去除特例。

特殊情况下的正常码

的特殊情况下的代码变得正常情况下

我觉得这种特殊的情况下去除单向链表不能在Python来完成，因为我们没有指针的概念（因此我不能在头部前走一步）？我对吗 ？

Answer 1

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

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

但是，它们都可以使用同名的属性（例如next）指向下一个项目。因此，当您遍历列表并且您位于第一个项目时，“上一个”项目就是列表本身，并且如果您需要删除第一个项目，则您正在操作其next属性。

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

Answer 2

你不能在Python中使用Linus的特定技巧，因为正如你所知，Python没有指针（就像这样）或者是一个操作符地址。但是，您仍然可以通过为列表添加一个虚拟头节点来消除列表头的特殊情况。您可以将其作为列表设计的固有部分，或者您可以通过创建额外节点并将其引用到第一个数据承载节点作为其下一个节点来实现。无论哪种方式，您可能要删除的所有节点都是内部节点，而不是特殊情况。

Answer 3

我在阅读你的问题时首先想到的是：你为什么要在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 4

你需要两个层次的间接做莱纳斯暗示的方式，但你有可能做到这一点在Python也许有一个对象的引用存储到这种物体或东西（指数为参考索引？）。也就是说，我认为它不会如此优雅或高效地映射到Python，并且使用对象来表示链接结构中的单个链接可能会非常浪费。

在Python的情况下，我只希望做更多的分支，以检查你从头部取出其中，除非有一些诀窍，我失踪案件。

至于自己实现链表，其实我觉得很多使用情况下，标准库是不够的。这里有一个例子：

...是格栅可能有10,000个细胞。由标准库提供的大多数链接列表没有经过优化，以每个列表32位索引的大小存储10,000个链接列表，因为它们试图提供允许单独使用链接列表的接口（不使用单独的备份数据结构以便像数组一样存储）。通常，链接列表的最有效使用是不拥有内存或管理任何资源的。它只是以一种辅助方式链接数据，这些数据已经在另一个数据结构中分配和管理，就像这样一个n元树中的128位（16字节）树节点，元素可以存储在层次结构的任何级别：

struct TreeNode 
{ 
    int32 parent;  // parent index or -1 for no parent 
    int32 first_child; // first child of this node or -1 
    int32 next_sibling; // next child for the parent node or -1 
    int32 element;  // element data stored in this node or -1 
         // if no data is associated 
}; 

所以有很多的用例实现自己的链表和其他链接的结构，该结构显著更有效的更窄，适用的用例（网格数据结构，八叉树，四树，图等），但是我不认为你可以在不容易让你使用两个或多个指针间接级别的语言中使用这个技巧。 Python固有地只有一个用于对象 - 与Java和C＃相同。您需要类似“对对象”或“的引用的索引，该索引指向对象”或“的索引，该索引指向对象”“的对象引用的索引。

另外，链接列表通常在语言中不那么有用，因为您不能管理所有内容都存储在内存中的语言，因为您最终可能会得到缓存未命中，从而导致迭代通过链接列表，否则如果每个列表节点在记忆在GC循环之后经常会发生，例如对于链接列表来说，要真正高效，就像Linux内核的情况一样，要求你能够很好地控制每个节点驻留在内存中的位置，以便列表遍历实际上大部分（如果不是完全的话）只是通过连续的记忆。否则，即使这意味着线性时间删除和中间插入，使用小型数组通常会更好。