爲什麼要使用鏈接列表而不是數組或矢量實現來實現堆棧或隊列？

如果陣列的空間約束，你會用向量執行棧或隊列的問題，那麼，爲什麼會有人使用實現這些數據結構的一個一個鏈接列表？任何現實生活中的例子都會很棒，如果不同於數組/矢量的實現，一些基本功能的Big O符號也會很好。

一個'LinkedList'是在Java中的隊列中，如果要動態生長的能力，你可能想使用它一個數組。 –

如果你想動態增長，你能不能用一個向量來實現隊列或堆棧？對不起，我更傾向於使用C++（從頭開始創建自己的堆棧或隊列） –

對於隊列，當在隊列中間操作數據（添加/刪除）時，鏈表將提供更快的結果：O（1）。如果使用數組或向量來實現，它將是O（n），因爲您必須移動其他元素來爲新元素創建空間，或者填充已刪除元素的空間。

2016-07-27 05:11:59 alexscasa

謝謝，我閱讀了關於堆棧的文章。但是，我並不認爲需要在隊列中插入隊列，因此隊列應該是先進先出算法，並且如果有的話可以插入到後端或前端「Deque」中。如果您開始添加其他功能，如insertbeforeLast，insertBeforeIndex等，那將是一般的鏈接列表。 –

對不起，我沒有在我的回覆中包含實現示例。如果它是優先級隊列，則需要操縱隊列的中間部分。具有高優先級的元素將需要添加在具有較低優先級的其他元素之前，但是在具有較高優先級的元素之後（在中間）。此外，在現實世界中，人們可能會退出隊列，因此隊列中間可能需要刪除。 – alexscasa

啊，優先隊列！一個很好的例子，使用鏈接列表來實現這一點非常有意義而且更容易，而不是處理所有索引轉換等。謝謝！ –

回答