请问你什么时候会用到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一大块，然后里面夹着一些辅助