什麼時候是鏈表最好的數據結構使用

Question

真的很像標題。我的問題是你可以舉一個例子，其中鏈接列表是最好的數據結構使用。我一直在努力思考任何問題，並且在我的代碼中，我幾乎總是使用hashmaps或者列表等。

http://bigocheatsheet.com/在這裏您可以看到Big O's的備忘單用於各種操作。就複雜性而言，鏈表不會比堆棧或隊列更好。所以我想知道什麼時候有人可以使用鏈表來比較這些？一個完美的答案會說：「想象一下，我試圖去做XYZ，如果我用數組來做它，它會看起來像{輸入一些代碼}，但是，如果我用鏈表來做，它會看起來像這樣{enter更多的代碼}。鏈接列表的複雜性或空間實際上更好。「等

我不想要一個答案，有人告訴我什麼是鏈接列表。我知道鏈表是​​什麼以及它們是如何實現的。

感謝

Answer 1

考慮一下，如果你有一個人的陣容，和中間的某個位置，你想添加的人很多。如果你使用了一個常規ArrayList，你需要將它後面的所有元素進行移位，所以O（N）因爲每個人都有索引！在LinkedList中，每個人都是O（1），O（N）到中間。鏈接列表在中間添加元素非常快，因爲您不需要重新索引任何內容，只需調整本地指針即可。

Answer 2

有人對C++標準模板庫進行了一次調查，發現鏈接列表是所有常用基本結構中使用最少的。所以你是對的，他們沒有太多的用處。當你不需要隨機訪問一個數組，當你不知道N或者在N上有一個合理的緊上界，並且當插入和刪除是通用的和時間關鍵的時候，它們非常有用。與數組一樣，中間插入是O（N），但實際操作要便宜很多（指針解引用而不是內存移位），開始處的插入是O（1），最後如果保留一個結束指針。