作者rosemary0401 (rosemary)
看板C_and_CPP
標題[問題] 什麼時候會需要用到linked list ??
時間Fri Aug 12 15:35:08 2016
請問你甚麼時候會用到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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1470987311.A.4EC.html
1F：推 LPH66: 當你會留著指向中間元素的指標時 (即是不需要 1 時) 08/12 15:41
請問甚麼scenario下，會留著指向中間elements的指標呢？
如果linked list裡面的每一個elements都需要另一個指標指向它，
以便將來新增/刪除，那豈不是還需要花很多額外的空間來做？
2F：推 bibo9901: 此O(n)和彼O(n)差很多. 再說其實你都講完了不是？ 08/12 15:41
3F：→ bibo9901: 另一個點是, 你可以很自由的改變linked list中的順序, 08/12 15:43
4F：→ bibo9901: 甚至是結構(tree,graph) 08/12 15:43
請問甚麼scenario下，會需要改變linked list中的順序呢？
我也可以在vector中透過swap來改變element的順序啊
※ 編輯: rosemary0401 (101.12.164.39), 08/12/2016 15:55:18
5F：→ bibo9901: 兩顆樹合併? 08/12 16:26
6F：推 chchwy: 雷電之類的卷軸射擊遊戲 管理螢幕上的子彈物件的時候 08/12 16:29
7F：推 Yshuan: OS課本不是也很多例子 08/12 16:38
8F：→ chchwy: linux管理分派的記憶體塊也是用list 08/12 16:39
9F：推 CaptainH: 管理process也是 08/12 16:42
10F：推 Clangpp: 你要寫 tree containers時會需要用到 08/12 16:58
11F：→ Caesar08: 可是vector在插入後，後面的element都要跟著move 08/12 17:16
12F：→ Caesar08: 如果capacity已經不夠了，那就要alloc，之後再move 08/12 17:16
13F：→ Caesar08: list在插入後，不需要move，頂多就是alloc 08/12 17:17
14F：→ Caesar08: 那這樣插入這動作，實際上是list比較快，而不是vector 08/12 17:17
15F：→ Caesar08: 再來，如果是C++11以前的code，那就沒有move，而是copy 08/12 17:18
16F：推 final01: 沒有 vector 就可以考慮 08/12 19:28
17F：→ MOONRAKER: vector咧 都去買便當了當然不用自己煮阿 08/12 19:54
18F：→ MOONRAKER: 看你要不要買便當過一輩子阿 08/12 19:54
19F：推 bluesoul: 當你需要在中間增減值的時候，vector搬動的成本很高 08/12 20:06
20F：→ bluesoul: 事先不知道總數大小時，也很適合，vector變更capacity的 08/12 20:07
21F：→ bluesoul: 成本很高 08/12 20:07
22F：推 oscar60111: linux中的task_struct 08/12 20:24
23F：推 bluesoul: 增減元素時，其他的元素的reference不會失效 08/12 20:27
24F：推 steve1012: 寫寫看LRU 08/12 21:02
25F：推 EdisonX: 最近用到的實例 :UI 上的 ListControl 編輯時. 08/13 00:16
26F：推 okgogogo: 觀察者模式會用到，註冊notify call back 08/13 00:38
27F：→ HolyBugTw: 當你把工具換成用C去思考，一切就改變了 08/16 14:17
28F：推 storm654321: vector 也是用linked list做出來的啊= = 08/17 10:23
29F：→ wlsh5701: 樓上 c++ vector的實作不一定是linked list吧 08/17 21:36
30F：→ Caesar08: storm654321: vector 也是用linked list做出來的啊 ??? 08/17 21:54
31F：→ ACMANIAC: 什麼時候 vector 是用 linked list 做出來的... 08/19 04:26
32F：推 s25g5d4: vector 有保證空間連續 怎麼會是 linked list... 08/19 23:40
33F：推 Hikkiaholic: 面試的時候。 08/22 08:26
34F：→ HolyBugTw: vector猜想會是malloc一大塊，然後裡面夾著一些輔助 08/24 12:17
35F：推 kevin190: DMA 08/25 00:56