用于实现堆栈的链表与动态数组 [英] 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)，而最坏情况下的 peek 成本为 O(1).这意味着如果您关心堆栈中任何单个操作的成本，这可能不是最好的方法.也就是说，分配很少，因此添加或删除 n 个元素的总成本可能比基于链表的方法中的相应成本更快.此外，这种方法的内存开销通常比链表的内存开销要好.如果您的动态数组只存储指向元素的指针，那么最坏情况下的内存开销会在填充一半元素时发生，在这种情况下，会有 n 个额外的指针(与使用链接的情况相同)list)，并且在动态数组已满的最佳情况下，没有空单元格，额外开销为 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) 保证.
• 链表的局部性不如动态数组的局部性.
• 假设两个都存储指向其元素的指针，动态数组的总开销可能小于链表的总开销.
• 如果直接存储元素，动态数组的总开销很可能大于链表的开销.

这些结构中没有一个明显比另一个更好".这真的取决于您的用例.找出哪个更快的最好方法是对两者进行计时，看看哪个表现更好.

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屋！