请问你什么时候会用到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