請問你甚麼時候會用到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)
作者:
LPH66 (-6.2598534e+18f)
2016-08-12 15:41:00當你會留著指向中間元素的指標時 (即是不需要 1 時)
作者:
bibo9901 (function(){})()
2016-08-12 15:41:00此O(n)和彼O(n)差很多. 再說其實你都講完了不是？另一個點是, 你可以很自由的改變linked list中的順序,甚至是結構(tree,graph)兩顆樹合併?
作者:
chchwy (mat)
2016-08-12 16:29:00雷電之類的卷軸射擊遊戲 管理螢幕上的子彈物件的時候
作者:
Yshuan (倚絃)
2016-08-12 16:38:00OS課本不是也很多例子
作者:
chchwy (mat)
2016-08-12 16:39:00linux管理分派的記憶體塊也是用list
作者:
CaptainH (Cannon)
2016-08-12 16:42:00管理process也是
作者:
Clangpp (Clang++)
2016-08-12 16:58:00你要寫 tree containers時會需要用到
作者:
Caesar08 (Caesar)
2016-08-12 17:16:00可是vector在插入後，後面的element都要跟著move如果capacity已經不夠了，那就要alloc，之後再movelist在插入後，不需要move，頂多就是alloc那這樣插入這動作，實際上是list比較快，而不是vector再來，如果是C++11以前的code，那就沒有move，而是copy
作者:
final01 (牛頓運動定律)
2016-08-12 19:28:00沒有 vector 就可以考慮
vector咧 都去買便當了當然不用自己煮阿看你要不要買便當過一輩子阿
作者:
bluesoul (å¿™æ»ä½ è€çˆ¸)
2016-08-12 20:06:00當你需要在中間增減值的時候，vector搬動的成本很高事先不知道總數大小時，也很適合，vector變更capacity的成本很高
作者: oscar60111 (還得努力學習) 2016-08-12 20:24:00
linux中的task_struct
作者:
bluesoul (å¿™æ»ä½ è€çˆ¸)
2016-08-12 20:27:00增減元素時，其他的元素的reference不會失效
作者:
EdisonX (卡卡獸)
2016-08-13 00:16:00最近用到的實例 :UI 上的 ListControl 編輯時.
觀察者模式會用到，註冊notify call back
vector 也是用linked list做出來的啊= =
作者: wlsh5701 (舞林樹枝) 2016-08-17 21:36:00
樓上 c++ vector的實作不一定是linked list吧
作者:
Caesar08 (Caesar)
2016-08-17 21:54:00storm654321: vector 也是用linked list做出來的啊 ???
作者:
ACMANIAC (請肥宅救救肥宅)
2016-08-19 04:26:00什麼時候 vector 是用 linked list 做出來的...
作者:
s25g5d4 (function(){})()
2016-08-19 23:40:00vector 有保證空間連續 怎麼會是 linked list...
vector猜想會是malloc一大塊，然後裡面夾著一些輔助