用链表还是动态数组来实现栈？

Question

我在学校最后一年开始复习数据结构和算法，以确保我掌握了所有内容。其中一个复习问题说“使用链表或动态数组实现堆栈，并解释为什么你做出了最佳的选择”。

对我来说，使用带有尾指针的列表来实现堆栈更直观，因为它可能需要经常调整大小。对于大量的数据来说，似乎使用列表是更好的选择，因为动态数组重新调整大小是一项昂贵的操作。此外，使用列表不需要分配比实际需要更多的空间，因此更节省空间。

然而，动态数组肯定可以更快地添加数据（除了需要重新调整大小的情况）。但是，我不确定使用数组是否总体上更快，还是只有在不需要重新调整大小的情况下才更快。

书中的解决方案表示，“对于存储非常大的对象，列表是更好的实现方式”，但我不明白为什么。

哪种方法最好？应该使用哪些因素来确定“最佳”实现方式？此外，我的逻辑有问题吗？

- Casey Patton

---

顺便提一下，链表的实现中不需要尾指针：您可以在链表头插入和删除元素。 - dmckee --- ex-moderator kitten

Answer 1

这里涉及到很多权衡，我认为这个问题没有一个“正确”的答案。

如果使用带尾指针的链表实现栈，那么push、pop或peek的最坏情况运行时间为O(1)。然而，每个元素都会有一些额外的开销（即指针），这意味着结构体上始终存在O(n)的开销。此外，根据内存分配器的速度，为栈分配新节点的成本可能是可感知的。另外，如果你不断地从栈中弹出所有元素，可能会因为缺乏连续存储空间而导致性能下降，因为不能保证链表单元在内存中连续存储。

如果使用动态数组实现栈，则push或pop的摊销运行时间为O(1)，peek的最坏情况成本为O(1)。这意味着如果你关心栈中任何单个操作的成本，这可能不是最佳方案。话虽如此，分配是不频繁的，因此添加或删除n个元素的总成本可能比基于链表的方法更快。此外，该方法的内存开销通常比链表的内存开销要好。如果你的动态数组只存储元素的指针，那么在最坏情况下，当填满一半元素时，会有n个额外的指针（与使用链表时相同），在动态数组都填满的最好情况下，没有空单元，额外开销为O(1)。另一方面，如果你的动态数组直接包含元素，则在最坏情况下内存开销可能更糟。最后，由于元素是连续存储的，如果你想要不断地push或pop栈中的元素，那么就有更好的局部性，因为所有元素在内存中都紧挨着彼此。

简而言之：

• 链表方法在每个操作上都保证了最坏情况的O(1)；动态数组具有摊销为O(1)的保证。
• 链表的局部性不如动态数组。
• 假设两种数据结构都存储指向其元素的指针，动态数组的总开销可能会比链表小。
• 如果元素直接存储，则动态数组的总开销可能会大于链表的总开销。

这两种结构并没有明显的“更好”的选择，而是取决于您的使用情况。要找出哪种更快，最好的方法是计时两者并看哪一个表现更好。

希望这可以帮助你！

- templatetypedef

---

提到局部性，我认为这是支持动态数组的胜利论点，值得赞扬。 - Baroudi Safwen

如果元素直接存储，动态数组的总开销可能会大于链表的开销。"直接存储"是什么意思？ - Leonid Vasilev

@Leonid Vasilyev 我设想的是一种类似于 C 或 C++ 的数组，其中数组元素直接存储在数组内部，而不像 Java 或 Python 数组那样，数组保存对实际元素的引用。 - templatetypedef

但是值类型的实例可能会占用相同的地址空间，无论它是动态数组还是链表节点，不是吗？ - Leonid Vasilev

@LeonidVasilyev 假设你有n个元素存储。想象一下你有一个动态数组，其中支持数组的大小为2n（也许你最近刚刚扩大了数组的大小）。总内存需要大约是一个指针（以知道数组在哪里），两个整数（以知道大小和容量）以及2n * sizeof(entry)字节的存储空间用于这些项。总共是2n * sizeof(entry) + 3 * sizeof(pointer)。对于链表，您拥有n * sizeof(entry)字节的元素，以及n * sizeof(pointer)字节的指针。总共为n *（sizeof(entry) + sizeof(pointer)）。 - templatetypedef

@LeonidVasilyev 这里的区别在于链表只在需要时为实际条目分配空间。这意味着，如果您有一个非常大的对象的链表，并将其与非常大的对象的动态数组进行比较，则会发现 n *（sizeof（entry）+ sizeof（pointer））< 2n * sizeof（entry）+ 3 * sizeof（pointer），从而节省空间。 - templatetypedef

Answer 2

调整动态数组的大小并不会很昂贵，如果您设计得好的话。

例如，为了扩展数组，如果它已满，则创建一个两倍大小的新数组，并复制项目。

最终，您将获得每添加N个项目的平均成本约为~3N。

- Mario Souza

Answer 3

对于小对象与大对象的问题，考虑如果您在堆栈上有小对象，那么使用链表需要多少额外空间。然后再考虑如果您在堆栈上有一堆大对象，需要多少额外的空间。

接下来，考虑基于动态数组的实现，同样的问题。

- Pillsy

---

因此，对于动态数组而言，为了避免频繁调整大小，需要留出额外的空间。如果使用大型对象，则需要留下大量的额外空间。另一方面，对于列表而言，您不必留下任何额外的空间，这使得列表成为如果对象非常大的更好的选择。这听起来正确吗？ - Casey Patton

如果你使用链表，每个链接都会占用空间，因此你需要一些额外的空间。 - Pillsy

Answer 4

重要的是在运行任务过程中调用malloc()的次数。获取一个内存块可能需要数百到数千条指令。(free()或GC中的时间应与此成比例。)此外，保持透视感。这可能是总时间的99％，也可能只有1％，具体取决于其他发生的事情。

- Mike Dunlavey

Answer 5

我认为你已经自己回答了这个问题。对于一个具有大量项目的堆栈，当仅向堆栈顶部添加一个额外项目时，动态数组将具有过多的开销成本（复制开销）。而使用列表只需简单地切换指针。

- David Cheung