: 推 LPH66: 当你会留着指向中间元素的指标时 (即是不需要 1 时) 08/12 15:41
: 请问什么scenario下，会留着指向中间elements的指标呢？
: 如果linked list里面的每一个elements都需要另一个指标指向它，
: 以便将来新增/删除，那岂不是还需要花很多额外的空间来做？
我也提一个使用情境好了
编译器当中表示程式码序列都是用 linklist
认真说的话中间其实还有一层叫做基本区块 (basic block)
一个基本区块里面只有最后一个指令是跳跃或分支指令
也就是大结构上是一个有向图表示程式流程 (很像初学程式在画的流程图)
这个有向图的每一个节点里是一条 linklist 表示基本区块里的各条指令
那在对程式码做最佳化的时候
一般都是整只程式扫一遍看有没有符合条件的再在附近进行操作
因此很自然的手上会已经有一个指向目前处理位置的指标
在这附近做增删改时就不需要花费太多功夫定位直接使用了
又或者一些跨基本区块的最佳化 (例如改变循环/条件判断的结构)
在处理的过程中都会有几个关键地方的指标会留着
(例如循环头、循环尾、或是要拆出分支或分支合并的地方等等)
因此在那附近做增删改拆并都不会有什么问题
也就是说, 这里的删除很少是“我要删掉串行中符合某某条件的指令”
而比较多是“扫一遍看看有什么要处理的弄一弄, 弄完把不要的删了”
搜寻的成本已经在其他操作中付过了直接把结果拿来用而已
我所谓的“会留着指向中间元素的指标”的状况就是这种
并不是说所有成员都要另外用个指标指著...
再说这种删除 99.9% 会是从串行的中间抽掉指令
就算不考虑搜寻的问题, 光这一点使用 linklist 就能大大省时了