我正在使用 Python 学习数据结构和算法。我了解到链表的优点是它没有最大节点数，这与其他语言中的数组不同。
由于 Python 会自动为我们调整列表的大小，因此优势已经为我们抽象掉了。
因此，我一直认为链表唯一的优势是在链表的前面或后面添加一个节点是 O(1)，而向列表添加一个元素可能最终Python 的复杂度为 O(n)，必须调整数组大小并复制每个元素。
但是，我刚刚了解到分摊时间复杂度在今天已经很流行了，而附加到列表的时间复杂度为 O(1)。因此，向列表添加元素实际上比向链表添加节点更快，因为在链表的前/后以外的任何位置添加节点都需要 O(n) 的时间复杂度。
那么，在数组/列表上使用链表有什么意义呢？
最佳答案
虽然当然可以制作一些它们可能有用的示例(在人为的情况下，也许您正在使用的工业 ASIC 需要它们)，但尤其是链表的琐碎实现作为一个例子而不是一个实际的结构存在，并且通常实际上是一个性能 tar 坑，因为它们会制造处理器缓存未命中1，导致性能比它们要差几个数量级出现在纸上
但是，它们是伟大的例子
- 清晰、完整且最小的指针教学演示
- 一些更有用的、可概括的概念
- 可以在不移动大量相邻数据的情况下插入中间数据
- 没有必要知道数据结构要使用多长时间
- 除了事件数据和下一个数据所在的位置之外，通常没有必要立即存储更多信息
链表在“硬”计算机科学之外也可能有用，例如，它们可以有效地建模生物过程
注意事项
1。为此寻找一个精确的例子，但我记得谷歌的一个很好的演示，为什么他们不在内部使用一些 stdlib 来防止由于性能降低/错误增加而意外使用链表和其他一些类型
关于python - 什么时候链接列表优先于列表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/70337221/