为什么要使用链接列表而不是数组或矢量实现来实现堆栈或队列？

如果阵列的空间约束，你会用向量执行栈或队列的问题，那么，为什么会有人使用实现这些数据结构的一个一个链接列表？任何现实生活中的例子都会很棒，如果不同于数组/矢量的实现，一些基本功能的Big O符号也会很好。

一个'LinkedList'是在Java中的队列中，如果要动态生长的能力，你可能想使用它一个数组。 –

如果你想动态增长，你能不能用一个向量来实现队列或堆栈？对不起，我更倾向于使用C++（从头开始创建自己的堆栈或队列） –

对于队列，当在队列中间操作数据（添加/删除）时，链表将提供更快的结果：O（1）。如果使用数组或向量来实现，它将是O（n），因为您必须移动其他元素来为新元素创建空间，或者填充已删除元素的空间。

2016-07-27 05:11:59 alexscasa

谢谢，我阅读了关于堆栈的文章。但是，我并不认为需要在队列中插入队列，因此队列应该是先进先出算法，并且如果有的话可以插入到后端或前端“Deque”中。如果您开始添加其他功能，如insertbeforeLast，insertBeforeIndex等，那将是一般的链接列表。 –

对不起，我没有在我的回复中包含实现示例。如果它是优先级队列，则需要操纵队列的中间部分。具有高优先级的元素将需要添加在具有较低优先级的其他元素之前，但是在具有较高优先级的元素之后（在中间）。此外，在现实世界中，人们可能会退出队列，因此队列中间可能需要删除。 – alexscasa

啊，优先队列！一个很好的例子，使用链接列表来实现这一点非常有意义而且更容易，而不是处理所有索引转换等。谢谢！ –

回答