XOR連結リスト

XOR連結リストとは

XOR連結リスト（XOR linked list）は、プログラミングにおけるデータ構造の一種で、双方向連結リストのメモリ効率を向上させるために考案されました。通常の双方向連結リストでは、各ノードが前後のノードのアドレスを保持するため、2つのポインタが必要となります。しかし、XOR連結リストでは、ビット毎の排他的論理和（XOR）演算を利用することで、これらの情報を1つのポインタフィールドに圧縮します。

仕組み

通常の双方向連結リストでは、以下のように各ノードが前後のノードへのポインタを持っています。


... A B C D E ...
> next > next > next >
< prev < prev < prev <


一方、XOR連結リストでは、各ノードが持つのは前後のノードのアドレスをXOR演算した値です。


... A B C D E ...
<--> A⊕C <-> B⊕D <-> C⊕E <->


ここで、⊕はXOR演算を表します。

この構造でリストを走査するには、現在見ているノードと、一つ前に走査したノードのアドレスが必要です。例えば、現在Cを見ており、前にBを走査していた場合、BのアドレスとCのリンクフィールドの値(B⊕D)から、Dのアドレスを計算できます。逆方向の走査も同様に行えます。

リストの走査を開始するには、連続する2つのノードのアドレスを知る必要があります。1つのノードのアドレスだけでは、リスト上を移動できません。これは、どちらの方向に走査しているかを判断するためです。

XOR連結リストの問題点

XOR連結リストには、以下のような問題点があります。

デバッグの困難さ: 一般的なデバッガでは、XOR連結リストを追跡できないため、デバッグが難しくなります。
コードの複雑化: メモリ使用量を削減できる一方で、コードの複雑性が増し、保守が難しくなります。
ガベージコレクションの制限: 多くのガベージコレクション手法では、実際のポインタでないと正しく機能しません。
型変換の必要性: ポインタ型のXOR演算が定義されていない場合（例えばC言語）、ポインタ型と整数型の間で型変換が必要になります。
走査の制限: リストを走査する場合、常に1つ前のノードのアドレスを保持しておく必要があります。
ノードの操作の制限: 例えば、別の構造体からXOR連結リスト上のノードのアドレスを取得した場合、そのノードをリストから外したり、他のノードを挿入したりする操作が困難です。

実用性

近年、コンピュータのメモリ容量が増大しているため、XOR連結リストは、メモリが限られた一部の組み込みシステム以外では、あまり利用されなくなってきています。組み込みシステムでも、より実用的なUnrolled linked listが使われることが多くなっています。Unrolled linked listは、キャッシュヒット率を向上させ、ランダムアクセス性能も向上させるという利点があります。

特徴

1つのノードからの走査: リスト上の1つのノードのアドレスだけが分かっている状態では、他のノードのアドレスを取得することはできません。
走査方法: あるノードから次のノードに移動するには、XOR演算を2回行えばよく、どちらの方向でも同じ処理になります。
例：{…B C D…} というリストで、レジスタR1に現在のノードCのアドレス、R2に前のノードのアドレスと現在のノードのアドレスのXOR（C⊕D）が格納されているとします。

X R2,Link R2 <- C⊕D ⊕ B⊕D (すなわち、B⊕C)
XR R1,R2 R1 <- C ⊕ B⊕C (すなわち、B)

ここで、Linkは現在ノードのリンクフィールド（B⊕D）です。
終端の処理: リストの終端は、次のノードのアドレスがゼロであるとします（{0 A B C…}）。Aのリンクフィールドは0⊕Bとなり、得られたアドレスがゼロかどうかをチェックする必要があります。また、リストの終端が走査に対して自動的に反射するようにすることも可能です。その場合、終端ノードのリンクフィールドをゼロにしておきます。

XOR演算の性質

XOR演算の以下の性質が、XOR連結リストの動作を支えています。

X⊕X = 0
X⊕0 = X
X⊕Y = Y⊕X
* (X⊕Y)⊕Z = X⊕(Y⊕Z)

これらの性質により、R2には常に現在ノードのアドレスと1つ前のノードのアドレスのXORが格納され、リンクフィールドの値とXORすることで、次のノードのアドレスを得ることが可能になります。

変種

XOR連結リストの考え方は、XOR演算に限らず、同様の性質を持つ他の二項演算にも応用できます。

加算連結リスト

各ノードが持つリンクフィールドに、前後のノードのアドレスを加算した値を格納します。


... A B C D E ...
<--> A+C <-> B+D <-> C+E <->


この場合、次のノードのアドレスは、1つ前のノードのアドレスを、現在ノードのリンクフィールドの値から減算することで得られます。

減算連結リスト

各ノードが持つリンクフィールドに、前後のノードのアドレスを減算した値を格納します。


... A B C D E ...
<--> C-A <-> D-B <-> E-C <->


この場合、走査する方向によって処理が異なります。順方向の場合、現在のリンクフィールドの値に1つ前のノードのアドレスを加算します。逆方向の場合、現在のリンクフィールドの値を1つ前のノードのアドレスから減算します。

減算連結リストの利点として、リスト全体を移動させた際に、リンクフィールドを変更する必要がないという点が挙げられます。また、C言語ではポインタ型を整数型にキャストする必要がありません。

まとめ

XOR連結リストは、メモリ使用量を削減する興味深いデータ構造ですが、その複雑さから、現在ではあまり利用されていません。しかし、その背後にある数学的な原理は、他のデータ構造やアルゴリズムにも応用できる重要な概念です。

もう一度検索