[問題] 什麼時候會需要用到linked list ??

[rosemary0401 (rosemary)]

請問你甚麼時候會用到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)


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.164.39
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1470987311.A.4EC.html
推 LPH66: 當你會留著指向中間元素的指標時 (即是不需要 1 時)
請問甚麼scenario下，會留著指向中間elements的指標呢？

如果linked list裡面的每一個elements都需要另一個指標指向它，
以便將來新增/刪除，那豈不是還需要花很多額外的空間來做？

推 bibo9901: 此O(n)和彼O(n)差很多. 再說其實你都講完了不是？
→ bibo9901: 另一個點是, 你可以很自由的改變linked list中的順序,
→ bibo9901: 甚至是結構(tree,graph)
請問甚麼scenario下，會需要改變linked list中的順序呢？
我也可以在vector中透過swap來改變element的順序啊
※ 編輯: rosemary0401 (101.12.164.39), 08/12/2016 15:55:18
→ bibo9901: 兩顆樹合併?
推 chchwy: 雷電之類的卷軸射擊遊戲 管理螢幕上的子彈物件的時候
推 Yshuan: OS課本不是也很多例子
→ chchwy: linux管理分派的記憶體塊也是用list
推 CaptainH: 管理process也是
推 Clangpp: 你要寫 tree containers時會需要用到
→ Caesar08: 可是vector在插入後，後面的element都要跟著move
→ Caesar08: 如果capacity已經不夠了，那就要alloc，之後再move
→ Caesar08: list在插入後，不需要move，頂多就是alloc
→ Caesar08: 那這樣插入這動作，實際上是list比較快，而不是vector
→ Caesar08: 再來，如果是C++11以前的code，那就沒有move，而是copy
推 final01: 沒有 vector 就可以考慮
→ MOONRAKER: vector咧 都去買便當了當然不用自己煮阿
→ MOONRAKER: 看你要不要買便當過一輩子阿
推 bluesoul: 當你需要在中間增減值的時候，vector搬動的成本很高
→ bluesoul: 事先不知道總數大小時，也很適合，vector變更capacity的
→ bluesoul: 成本很高
推 oscar60111: linux中的task_struct
推 bluesoul: 增減元素時，其他的元素的reference不會失效
推 steve1012: 寫寫看LRU
推 EdisonX:  最近用到的實例 :UI 上的 ListControl 編輯時.
推 okgogogo: 觀察者模式會用到，註冊notify call back
→ HolyBugTw: 當你把工具換成用C去思考，一切就改變了
推 storm654321: vector 也是用linked list做出來的啊= =
→ wlsh5701: 樓上 c++ vector的實作不一定是linked list吧
→ Caesar08: storm654321: vector 也是用linked list做出來的啊  ???
→ ACMANIAC: 什麼時候 vector 是用 linked list 做出來的...
推 s25g5d4: vector 有保證空間連續 怎麼會是 linked list...
推 Hikkiaholic: 面試的時候。
→ HolyBugTw: vector猜想會是malloc一大塊，然後裡面夾著一些輔助
推 kevin190: DMA