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

[LPH66 (-6.2598534e+18f)]

: 推 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
推 EdisonX: 這篇讓我產生另個疑問...VS 後期的 Debugger 可以把執行
→ EdisonX: 到的地方往上面拉(回溯) , 不知道是怎做的.單純 Stack ??
推 LiloHuang: 我記得往回拉只是改 eip 強制跳回去，變數內容沒回朔@@
推 james732: 推
→ VictorTom: VC/WinDbg都只是拉ip回去, 直接改ip也有同樣效果:)