链接列表与实现堆栈的动态数组 [英] Linked list vs. dynamic array for implementing a stack

问题描述

在我最后一年的学校开始之前，我已经开始审查数据结构和算法，以确保我处于一切之上。一个评论问题说使用链表或动态数组来实现堆栈，并解释为什么你做出了最佳选择。

I've started reviewing data structures and algorithms before my final year of school starts to make sure I'm on top of everything. One review problem said "Implement a stack using a linked list or dynamic array and explain why you made the best choice".

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

To me, it seemed more intuitive to use a list with a tail pointer to implement a stack since it may need to be resized often. It seems like for a large amount of data, a list is the better choice since a dynamic array re-size is an expensive operation. Additionally, with a list, you don't need to allocate any more space than you actually need so it's more space efficient.

然而，动态数组肯定会允许添加数据更快（除了需要调整大小之外）。但是，我不知道使用数组是否整体更快，或者只有在不需要调整大小的情况下才能使用。

However, a dynamic array would definitely allow for adding data far quicker (except when it needs to be resized). However, I'm not sure if using an array is overall quicker, or only if it doesn't need to be resized.

大对象，列表是更好的实现但我不明白为什么。

The book's solution said "for storing very large objects, a list is a better implementation" but I don't understand why.

哪种方式最好？应该使用哪些因素来确定哪个实施是最好的？此外，我的任何逻辑都在这里吗？

Which way is best? What factors should be used to determine which implementation is "best"? Also, is any of my logic here off?

推荐答案

这里涉及到许多权衡，我不认为有正确的答案这个问题。

There are many tradeoffs involved here and I don't think that there's a "correct" answer to this question.

如果您使用带有尾部指针的链接列表实现堆栈，那么最坏情况的运行时可以推送，弹出或窥视是O（1）。然而，每个元素将会有一些与之相关的额外开销（即指针），这意味着结构总是有O（n）开销。另外，根据内存分配器的速度，为堆栈分配新节点的成本可能是显着的。另外，如果你不断地从堆栈中弹出所有的元素，你可能会遇到一个性能不佳的地方，因为不能保证链表单元格将被连续存储在内存中。

If you implement the stack using a linked list with a tail pointer, then the worst-case runtime to push, pop, or peek is O(1). However, each element will have some extra overhead associated with it (namely, the pointer) that means that there is always O(n) overhead for the structure. Additionally, depending on the speed of your memory allocator, the cost of allocating new nodes for the stack might be noticeable. Also, if you were to continuously pop off all the elements from the stack, you might have a performance hit from poor locality, since there is no guarantee that the linked list cells will be stored contiguously in memory.

如果您使用动态数组实现堆栈，则推送或弹出的摊销运行时是O（1），偷看的最坏情况是O（ 1）。这意味着如果您关心堆栈中任何单个操作的成本，这可能不是最佳方法。也就是说，分配不频繁，因此添加或删除n个元素的总成本可能比基于链表的方法中相应的成本更快。另外，这种方法的内存开销通常要好于链表的内存开销。如果您的动态数组只存储指向元素的指针，那么最坏情况下的内存开销就会在填充一半的元素时发生，在这种情况下，会有n个额外的指针（与使用链接的情况相同）列表），并且在动态数组已满的最佳情况下，没有空单元格，额外的开销是O（1）。另一方面，如果您的动态数组直接包含元素，则最坏情况下，内存开销可能会更糟。最后，因为这些元素是连续存储的，所以如果你想从堆栈中连续推送或弹出元素，就会有更好的局部性，因为所有元素在内存中彼此相邻。

If you implement the stack with a dynamic array, then the amortized runtime to push or pop is O(1) and the worst-case cost of a peek is O(1). This means that if you care about the cost of any single operation in the stack, this may not be the best approach. That said, allocations are infrequent, so the total cost of adding or removing n elements is likely to be faster than the corresponding cost in the linked-list based approach. Additionally, the memory overhead of this approach is usually better than the memory overhead of the linked list. If your dynamic array just stores pointers to the elements, then the memory overhead in the worst-case occurs when half the elements are filled in, in which case there are n extra pointers (the same as in the case when you were using the linked list), and in the best case when the dynamic array is full there are no empty cells and the extra overhead is O(1). If, on the other hand, your dynamic array directly contains the elements, the memory overhead can be worse in the worst-case. Finally, because the elements are stored contiguously, there is better locality if you want to continuously push or pop elements from the stack, since all the elements are right next to each other in memory.

简而言之：

• 链表列表方法对每个操作都有最坏的O（1）保证;动态数组已经摊销了O（1）保证。


• 链表的位置不如动态数组的位置。


• 假设动态数组的总开销可能小于链表的总开销，假设两个存储指针指向其元素。


• 动态数组的总开销很可能如果元素直接存储，则大于链表的值。

• The linked-list approach has worst-case O(1) guarantees on each operation; the dynamic array has amortized O(1) guarantees.
• The locality of the linked list is not as good as the locality of the dynamic array.
• The total overhead of the dynamic array is likely to be smaller than the total overhead of the linked list, assuming both store pointers to their elements.
• The total overhead of the dynamic array is likely to be greater than that of the linked list if the elements are stored directly.

这两个结构都不比其他。这真的取决于你的用例。找出哪一个更快的最好方法是两次都能看到哪个效果更好。

Neither of these structures is clearly "better" than the other. It really depends on your use case. The best way to figure out which is faster would be to time both and see which performs better.

希望这有帮助！

这篇关于链接列表与实现堆栈的动态数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！