Re: [問題] 什麼時候會需要用到linked list ??
: 推 LPH66: 當你會留著指向中間元素的指標時 (即是不需要 1 時) 08/12 15:41
: 請問甚麼scenario下，會留著指向中間elements的指標呢？
: 如果linked list裡面的每一個elements都需要另一個指標指向它，
: 以便將來新增/刪除，那豈不是還需要花很多額外的空間來做？
我也提一個使用情境好了
編譯器當中表示程式碼序列都是用 linklist
認真說的話中間其實還有一層叫做基本區塊 (basic block)
一個基本區塊裡面只有最後一個指令是跳躍或分支指令
也就是大結構上是一個有向圖表示程式流程 (很像初學程式在畫的流程圖)
這個有向圖的每一個節點裡是一條 linklist 表示基本區塊裡的各條指令
那在對程式碼做最佳化的時候
一般都是整隻程式掃一遍看有沒有符合條件的再在附近進行操作
因此很自然的手上會已經有一個指向目前處理位置的指標
在這附近做增刪改時就不需要花費太多功夫定位直接使用了
又或者一些跨基本區塊的最佳化 (例如改變迴圈/條件判斷的結構)
在處理的過程中都會有幾個關鍵地方的指標會留著
(例如迴圈頭、迴圈尾、或是要拆出分支或分支合併的地方等等)
因此在那附近做增刪改拆併都不會有什麼問題
也就是說, 這裡的刪除很少是「我要刪掉串列中符合某某條件的指令」
而比較多是「掃一遍看看有什麼要處理的弄一弄, 弄完把不要的刪了」
搜尋的成本已經在其他操作中付過了直接把結果拿來用而已
我所謂的「會留著指向中間元素的指標」的狀況就是這種
並不是說所有成員都要另外用個指標指著...
再說這種刪除 99.9% 會是從串列的中間抽掉指令
就算不考慮搜尋的問題, 光這一點使用 linklist 就能大大省時了
--
將很小又單純的命令《Code》組合成函數《Function》。函數累積成更大更方便的元件《
Parts》，成為程式《App》。接著進行動態結合，相互通訊，打造出服務《Service》。
李奧納多知道，要得到結果，就必須持續進行非常單純的作業。為了展現出匹敵巨大建築
的技術，現在非得將面前的碎片組合起來。
知道這條路多麼遙遠的人，叫做極客《Geek》。
將這份尊貴具體呈現的人，叫做駭客《Hacker》。 －－記錄的地平線 Vol.9 p.299
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.13.222
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1471020262.A.1FF.html
推
08/13 00:46, , 1F
08/13 00:46, 1F
→
08/13 00:47, , 2F
08/13 00:47, 2F
推
08/13 01:29, , 3F
08/13 01:29, 3F
推
08/13 14:16, , 4F
08/13 14:16, 4F
→
08/13 14:33, , 5F
08/13 14:33, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：