问链接列表应该总是有尾指针吗？

EN

你是对的，尾巴指针永远不会伤害，也只能帮助你。然而，在这种情况下，一个人根本不需要尾巴指针。

如果使用链接列表来实现堆栈，则不需要尾指针，因为可以保证所有访问、插入和删除都发生在头端。尽管如此，人们还是可以使用带有尾指针的双链接列表，因为这是库或平台中的标准实现，内存很便宜，但不需要它。

链接列表通常是持久的和不可变的。事实上，在函数式编程语言中，这种用法无处不在。尾指针破坏了这两个属性。但是，如果您不关心不变性或持久性，那么包含一个尾指针几乎没有什么坏处。

对于链接列表，我很少使用尾指针，并且倾向于更频繁地使用单链接列表，在插入和删除堆栈样的push/pop模式(或仅从中间删除线性时间)就足够了。这是因为在我的常用用例中，尾指针实际上是昂贵的，就像将单链列表变成双链接列表是昂贵的一样。

通常情况下，单链接列表的通用情况用法可能存储数十万个链接列表，其中每个列表节点仅包含几个列表节点。我通常也不对链接列表使用指针。我在数组中使用索引，因为索引可以是32位，例如，占用64位指针空间的一半。我通常不会一次分配一个列表节点，而是使用一个大数组来存储所有节点，然后使用32位索引将节点链接到一起。

举个例子，想象一下一个视频游戏，它使用400x400网格来分割数百万个粒子，这些粒子相互移动和反弹，以加速碰撞检测。在这种情况下，一种非常有效的存储方法就是存储16万个单链表，在我的例子中，这意味着16万32位整数(大约640千字节)和每个粒子一个32位整数开销。现在，当粒子在屏幕上移动时，我们所要做的就是更新一些32位整数，以便将粒子从一个单元格移动到另一个单元格，如下所示：

..。使用粒子节点的next索引(“指针”)作为单元格中下一个粒子的索引，或者在粒子死后回收下一个空闲粒子(基本上是使用索引的空闲列表分配器实现)：

从一个单元格中删除线性时间并不是一种开销，因为我们通过迭代单元中的粒子来处理粒子逻辑，所以双链接列表只会增加一种在我的情况下完全没有好处的开销，就像尾巴对我也没有好处一样。

一个尾指针将使网格的内存使用量增加一倍，并增加缓存丢失的数量。它还需要插入以要求分支检查列表是否为空，而不是没有分支。使之成为一个双链接列表将使每个粒子的列表开销增加一倍。在我使用链接列表的90%时间里，它都是针对这样的情况的，所以一个尾指针实际上是相当昂贵的存储。

因此，在我首先使用链接列表的大多数上下文中，4-8字节实际上并不简单。因为如果您使用数据结构来存储大量的元素，那么4-8字节可能并不总是可以忽略不计。实际上，我使用链接列表来减少所需的内存分配数和内存量，而不是存储160,000个动态数组，这些动态数组将用于具有爆炸性内存使用的网格(通常是一个指针加两个整数--至少每个网格单元格加上堆分配，而不是每个单元格只有一个整数和零堆分配)。

我经常发现，当LLs在这些情况下由于缺乏连续性而成为一个糟糕的选择时，很多人会找到链接列表，因为它们的固定时间复杂性与前/中移除和前/中插入相关。从性能的角度来看，LLs对我来说是一种能力，只要操作几个指针就可以将一个元素从一个列表移动到另一个列表，并且能够在没有可变大小内存分配器的情况下实现可变大小的数据结构(例如，由于每个节点都有相同的大小，我们可以使用空闲列表)。如果每个列表节点都是针对一个通用的分配器单独分配的，那么通常情况下，链接列表的性能要比其他列表糟糕得多，而且通常是通过误导性的使用，最终在诸如C++这样的语言中获得了不好的声誉。

相反，我建议，在大多数情况下，链接列表作为对简单的替代方案的非常有效的优化，最有用的表单通常是单链接的，只需要一个头指针，并且不需要为每个节点分配通用内存，而是可以将每个节点已经分配的内存(例如，来自预先分配的大数组)集中起来。另外，在这些情况下，每个SLL通常会存储非常少的元素，比如连接到图节点的边缘(许多微小的链接列表，而不是一个庞大的链接列表)。

同样值得记住的是，我们现在有很多DRAM，但这是第二种最慢的内存。当涉及到64字节高速缓存行的L1缓存时，每个核心的容量仍然大约为64 KB。因此，在性能关键区域，如上面的粒子sim乘以数百万倍，如果这意味着将两倍多的节点存储到缓存行中的差别，那么这些字节节省真的很重要。