operating-system - 更快的访问时间，堆栈还是堆？

Question

Steven Skienna 的经典算法设计手册指出，链表在创建方面比动态数组快。这是堆性能更快的原因吗？谁能从操作系统的角度解释一下？

Answer 1

链接列表和动态数组都在堆上维护。在动态数组中插入可能会导致数组增长，而对于链接列表，它将被添加到末尾。即使插入在链表的中间，也需要时间搜索，稍后只需一个操作即可将指针添加到前一个节点。链接列表不需要调整相邻的内存位置。

动态数组 - Wiki

与链表相比，动态数组具有更快的索引（恒定时间与线性时间），并且由于改进了引用的局部性，通常迭代更快；但是，动态数组在任意位置插入或删除需要线性时间，因为必须移动所有后续元素，而链表可以在恒定时间内完成此操作。下文变体中讨论的间隙缓冲区和分层向量变体减轻了这一缺点。此外，在高度碎片化的内存区域中，为大型动态数组找到连续空间可能会很昂贵或不可能，而链表不需要连续存储整个数据结构。