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

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