XOR連結リスト

XOR連結リスト（英: XOR linked list）は、プログラミングにおけるデータ構造の一種。ビット毎の排他的論理和 (XOR) の特徴を生かして、双方向連結リストに必要なメモリ量を削減する。なお、以下ではXOR演算を ⊕ と記述する。
概要.
通常の双方向連結リストは、リスト上の前後のノードのアドレスを各ノードに格納する。従って、アドレス格納フィールドを2つ必要とする。
XOR連結リストでは、同じ情報を1つのアドレスフィールドに圧縮する。このとき、"prev" と "next" のアドレスについてビット毎のXOR演算を行った値をそのフィールドに格納する。
このリストを左から右に走査するとして、現在 C を見ているとすると、前に走査した B のアドレスが分かっており、同時に C のリンクフィールドの値 (B⊕D) も分かっている。これらの情報から D のアドレスが求められ、リストの走査を続行できる。逆方向からの走査も同様である。
リスト上のある位置からどちらかの方向に走査を開始するには、連続する2つのノードのアドレスを知る必要がある。ひとつのノードのアドレスが分かっているだけでは、リスト上を移動できない。2つのノードがリスト上どういう順序で連結されているかが分からないと、どちらの方向に走査しているのか分からなくなる。
XOR連結リストは、以下のような問題を抱えている。
コンピュータのメモリは増大しているため、XOR連結リストは一部の組み込みシステムのようなメモリが限られている場合以外では無用となっている。組み込みシステムでも、Unrolled linked list の方がより実用的である（キャッシュヒット率を向上させ、ランダムアクセス性能が向上するという利点もある）。
なぜうまくいくのか?
鍵となるのは、最初の命令と以下のようなXORの性質である。
R2 レジスタには、現在のノード C のアドレスと1つ前のノードのアドレス P の XOR、すなわち C⊕P が常に格納されている。ノードのリンクフィールドには、前後のノードのアドレスのXOR、すなわち L⊕R が格納されている。従って、R2 (C⊕P) と現在のリンクフィールド (L⊕R) の XOR を求めると C⊕P⊕L⊕R となる。
どちらの場合も、残るのは現在のアドレスと次のノードのアドレスの XOR である。これを R1 にある現在ノードのアドレスと XOR することで次のノードのアドレスだけが残る。このとき、R2 には新たな現在ノードと1つ前のノードのアドレスの XOR が残されている。
変種.
XOR連結リストの考え方は、同様の性質を持つ任意の二項演算にも応用できる。XORを加算や減算に置換したものは、XORの場合とは微妙に異なるが、ほぼ同等な機能を持つ。
加算連結リスト.
この場合、次のノードのアドレスは、1つ前のノードのアドレスを現在ノードのリンクフィールドの値から減算することで得られる。XOR連結リストとほぼ同じだが、終端ノードのリンクフィールドをゼロにしても反射することはない。なお、加算によってオーバーフローを起こしても何ら問題はない。
減算連結リスト.
この場合、走査する方向によって処理が異なる。順方向の場合、現在のリンクフィールドの値に1つ前のノードのアドレスを加算することで、次のノードのアドレスが得られる。逆方向の場合、現在のリンクフィールドの値を1つ前のノードのアドレスから減算することで、次のノードのアドレスが得られる。
減算連結リストは、リスト全体をノード間の位置関係を保ったままメモリ上で移動させた場合、リンクフィールドに全く変更を加える必要がない。これはXOR連結リストにも普通の連結リストにもない利点である。また、C言語ではポインタ型を整数型にキャストする必要もない。C言語では2つのポインタの減算結果は自動的に整数になるからである。