XOR連結リスト

XOR連結リスト（英: XOR linked list）は、プログラミングにおけるデータ構造の一種。ビット毎の排他的論理和 (XOR) の特徴を生かして、双方向連結リストに必要なメモリ量を削減する。なお、以下ではXOR演算を ⊕ と記述する。

概要

通常の双方向連結リストは、リスト上の前後のノードのアドレスを各ノードに格納する。従って、アドレス格納フィールドを2つ必要とする。

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

XOR連結リストでは、同じ情報を1つのアドレスフィールドに圧縮する。このとき、"prev" と "next" のアドレスについてビット毎のXOR演算を行った値をそのフィールドに格納する。

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

このリストを左から右に走査するとして、現在 C を見ているとすると、前に走査した B のアドレスが分かっており、同時に C のリンクフィールドの値 (B⊕D) も分かっている。これらの情報から D のアドレスが求められ、リストの走査を続行できる。逆方向からの走査も同様である。

リスト上のある位置からどちらかの方向に走査を開始するには、連続する2つのノードのアドレスを知る必要がある。ひとつのノードのアドレスが分かっているだけでは、リスト上を移動できない。2つのノードがリスト上どういう順序で連結されているかが分からないと、どちらの方向に走査しているのか分からなくなる。

XOR連結リストは、以下のような問題を抱えている。

• 汎用的なデバッガはXOR連結リストを追うことができないので、デバッグが難しくなる。
• メモリ使用量を削減するのと引き換えにコードの複雑性が増し、コード保守が大変になる。
• 多くのガベージコレクション手法では、実際のポインタでないとうまく機能しない。
• ポインタ型のXOR演算は定義されていないことがある（例えば、C言語）ので、ポインタ型と整数型の間で型変換が必要となる。
• リスト上を走査する場合、常に1つ前のノードのアドレスを保持していないと、走査できない。
• 例えば、別の構造体にXOR連結リスト上のノードのアドレスがある場合、その構造体からノードが得られても、そのノードをリストから外す操作やそのノードの次に別のノードを挿入する操作が不可能である。例えば、使用中のプロセス制御ブロック(PCB)を対応するプロセスの終了時に使用中リストからフリーリストに繋ぎ変えるといった場合、使用中PCBリストはXOR連結リストでは構成できない。

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

特徴

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

 X  R2,Link    R2 <- C⊕D ⊕ B⊕D （すなわち、B⊕C となる。"Link" は現在ノードのリンク
                                   フィールドであり、B⊕D が格納されている）
 XR R1,R2      R1 <- C ⊕ B⊕C    （すなわち、B が得られる）

• リストの終端は次のノードのアドレスがゼロであるとしておく（{0 A B C…}）。すなわち、A のリンクフィールドは 0⊕B となる。従って、上記の命令列の後で得られたアドレスがゼロかどうかをチェックしなければならない。この場合、リストの先頭を保持するときに A のアドレスだけを保持すればよい（1つ前のアドレスがゼロであることが自明であるため）。
• 別の方式として、リスト終端が走査に対して自動的に反射するようにもできる。この場合は端のノードのリンクフィールドをゼロにしておく。例えば、B から A の方向に移動してきたとき、A のリンクフィールドがゼロであれば、上記命令列を実施すると B のアドレスが得られる。ただしこの場合、リストの先頭を保持するときに A と B のアドレスを保持しておく必要がある（A だけでは次のノードのアドレスが全く分からないため）。

なぜうまくいくのか?

鍵となるのは、最初の命令と以下のようなXORの性質である。

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

R2 レジスタには、現在のノード C のアドレスと1つ前のノードのアドレス P の XOR、すなわち C⊕P が常に格納されている。ノードのリンクフィールドには、前後のノードのアドレスのXOR、すなわち L⊕R が格納されている。従って、R2 (C⊕P) と現在のリンクフィールド (L⊕R) の XOR を求めると C⊕P⊕L⊕R となる。

• 1つ前のノードが L であった場合、P と L は同じなので打ち消しあい、C⊕R が残る。
• 1つ前のノードが R であった場合、P と R は同じなので打ち消しあい、C⊕L が残る。

どちらの場合も、残るのは現在のアドレスと次のノードのアドレスの XOR である。これを R1 にある現在ノードのアドレスと XOR することで次のノードのアドレスだけが残る。このとき、R2 には新たな現在ノードと1つ前のノードのアドレスの XOR が残されている。

変種

XOR連結リストの考え方は、同様の性質を持つ任意の二項演算にも応用できる。XORを加算や減算に置換したものは、XORの場合とは微妙に異なるが、ほぼ同等な機能を持つ。

加算連結リスト

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

この場合、次のノードのアドレスは、1つ前のノードのアドレスを現在ノードのリンクフィールドの値から減算することで得られる。XOR連結リストとほぼ同じだが、終端ノードのリンクフィールドをゼロにしても反射することはない。なお、加算によってオーバーフローを起こしても何ら問題はない。

減算連結リスト

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

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

減算連結リストは、リスト全体をノード間の位置関係を保ったままメモリ上で移動させた場合、リンクフィールドに全く変更を加える必要がない。これはXOR連結リストにも普通の連結リストにもない利点である。また、C言語ではポインタ型を整数型にキャストする必要もない。C言語では2つのポインタの減算結果は自動的に整数[1]になるからである。

脚注

1. ただし、そのポインタが指す型に依った値になる。また、標準では1個の配列の中を指すポインタ同士でなければならないことになっている。

関連項目

• XOR交換アルゴリズム