請問你甚麼時候會用到linked list
網路上找過一些資料，都沒有找到很好的答案
很多人都說
"當你需要在中間大量新增刪除element的時候，然後不需要做random access的時候，
因為linked list新增刪除是O(1)，在linked list random access是O(N)"
但是你也要找到欲新增/刪除的那個點才能刪除它，所以整體time complexity應為O(N)
比方說假設你有以下linked list：
1 -> 5 -> 3 -> 15 -> 2 -> ... -> NULL
↑
head
要在上面linked list刪除value為2的element，必須要
1. 找到value為2的element (Time Complexity: O(N))
2. 刪除該element (Time Complexity: O(1))
這樣感覺上還倒不如用vector
當然在vector在push_back時，有些時候需要re-allocate (long term而言還是O(1))
尤其在中間做新增/刪除時會需要shift elements (O(N))
簡言之，到底甚麼時候用linked list呢？
(我目前想到大概就是用來實作queue或tree的時候，其他scenario不會用到linked list)

當你會留著指向中間元素的指標時 (即是不需要 1 時)

此O(n)和彼O(n)差很多. 再說其實你都講完了不是？另一個點是, 你可以很自由的改變linked list中的順序,甚至是結構(tree,graph)兩顆樹合併?

雷電之類的卷軸射擊遊戲 管理螢幕上的子彈物件的時候

OS課本不是也很多例子

linux管理分派的記憶體塊也是用list

管理process也是

你要寫 tree containers時會需要用到

可是vector在插入後，後面的element都要跟著move如果capacity已經不夠了，那就要alloc，之後再movelist在插入後，不需要move，頂多就是alloc那這樣插入這動作，實際上是list比較快，而不是vector再來，如果是C++11以前的code，那就沒有move，而是copy

沒有 vector 就可以考慮

vector咧 都去買便當了當然不用自己煮阿看你要不要買便當過一輩子阿

當你需要在中間增減值的時候，vector搬動的成本很高事先不知道總數大小時，也很適合，vector變更capacity的成本很高

linux中的task_struct

增減元素時，其他的元素的reference不會失效

寫寫看LRU

最近用到的實例 :UI 上的 ListControl 編輯時.

觀察者模式會用到，註冊notify call back

當你把工具換成用C去思考，一切就改變了

vector 也是用linked list做出來的啊= =

樓上 c++ vector的實作不一定是linked list吧

storm654321: vector 也是用linked list做出來的啊 ???

什麼時候 vector 是用 linked list 做出來的...

vector 有保證空間連續 怎麼會是 linked list...

面試的時候。

vector猜想會是malloc一大塊，然後裡面夾著一些輔助

DMA