: 推 LPH66: 當你會留著指向中間元素的指標時 (即是不需要 1 時) 08/12 15:41
: 請問甚麼scenario下，會留著指向中間elements的指標呢？
: 如果linked list裡面的每一個elements都需要另一個指標指向它，
: 以便將來新增/刪除，那豈不是還需要花很多額外的空間來做？
我也提一個使用情境好了
編譯器當中表示程式碼序列都是用 linklist
認真說的話中間其實還有一層叫做基本區塊 (basic block)
一個基本區塊裡面只有最後一個指令是跳躍或分支指令
也就是大結構上是一個有向圖表示程式流程 (很像初學程式在畫的流程圖)
這個有向圖的每一個節點裡是一條 linklist 表示基本區塊裡的各條指令
那在對程式碼做最佳化的時候
一般都是整隻程式掃一遍看有沒有符合條件的再在附近進行操作
因此很自然的手上會已經有一個指向目前處理位置的指標
在這附近做增刪改時就不需要花費太多功夫定位直接使用了
又或者一些跨基本區塊的最佳化 (例如改變迴圈/條件判斷的結構)
在處理的過程中都會有幾個關鍵地方的指標會留著
(例如迴圈頭、迴圈尾、或是要拆出分支或分支合併的地方等等)
因此在那附近做增刪改拆併都不會有什麼問題
也就是說, 這裡的刪除很少是「我要刪掉串列中符合某某條件的指令」
而比較多是「掃一遍看看有什麼要處理的弄一弄, 弄完把不要的刪了」
搜尋的成本已經在其他操作中付過了直接把結果拿來用而已
我所謂的「會留著指向中間元素的指標」的狀況就是這種
並不是說所有成員都要另外用個指標指著...
再說這種刪除 99.9% 會是從串列的中間抽掉指令
就算不考慮搜尋的問題, 光這一點使用 linklist 就能大大省時了