XOR連結リスト
発想が面白い
「あるノードは前後のノードのアドレスを XOR したものを持つ」
これによりリストを構築して、メモリ使用量を削減する
A, B, C とあるとき、次のように持つ
code:text
A has 0 ^ &B
B has &A ^ &C
C has &B ^ 0
B から C は &A ^ B.linkと計算する
XOR演算の、結合則、可換則、X ^ X = 0、0 ^ X = X を利用して
&A ^ (&A ^ &C) =(&A ^ &A) ^ &C) = 0 ^ &C = &Cとなる
XORだけでなく、加算と減算でも実現できるらしい
実用上は Unrolled Linked List の方がメリットがあるとか
隣接する2ノードが既知ではないといじれないのがかなり不便そう
Wikipedia にも書かれているような、Linux などで見られる未使用リスト、使用リストの2種を作って、ノードをリスト間で移動する、などがやりにくい