list)は、プログラミングにおけるデータ構造の一種。特徴を生かして、双方向連結リストに必要なメモリ量を削減する。概要[編集]通常の双方向連結リストは、リスト上の前後のノードのアドレスを各ノードに格納する。従って、アドレス格納フィールドを2つ必要とする。<–XOR連結リストでは、同じ情報を1つのアドレスフィールドに圧縮する。アドレスについてビット毎のXOR演算を行った値をそのフィールドに格納する。アドレスが求められ、リストの走査を続行できる。逆方向からの走査も同様である。リスト上のある位置からどちらかの方向に走査を開始するには、連続する2つのノードのアドレスを知る必要がある。ひとつのノードのアドレスが分かっているだけでは、リスト上を移動できない。2つのノードがリスト上どういう順序で連結されているかが分からないと、どちらの方向に走査しているのか分からなくなる。XOR連結リストは、以下のような問題を抱えている。汎用的なデバッガはXOR連結リストを追うことができないので、デバッグが難しくなる。メモリ使用量を削減するのと引き換えにコードの複雑性が増し、コード保守が大変になる。多くのガベージコレクション手法では、実際のポインタでないとうまく機能しない。ポインタ型のXOR演算は定義されていないことがある(例えば、C言語)ので、ポインタ型と整数型の間で型変換が必要となる。リスト上を走査する場合、常に1つ前のノードのアドレスを保持していないと、走査できない。別の構造体にXOR連結リスト上のノードのアドレスがある場合、その構造体からノードが得られても、そのノードをリストから外す操作やそのノードの次に別のノードを挿入する操作が不可能である。使用中のプロセス制御ブロック(PCB)を対応するプロセスの終了時に使用中リストからフリーリストに繫ぎ変えるといった場合、使用中PCBリストはXOR連結リストでは構成できない。コンピュータのメモリは増大しているため、XOR連結リストは一部の組み込みシステムのようなメモリが限られている場合以外では無用となっている。方がより実用的である(キャッシュヒット率を向上させ、ランダムアクセス性能が向上するという利点もある)。特徴[編集]リスト上の1つのノードだけが分かった状態では、そのリスト上の他のノードのアドレスは得られない。あるノードから次のノードに移動(走査)していくには、XOR演算を2回行えばよく、どちらの方向でも同じ処理になる。したもの(C⊕D)が格納されているとする。命令で表すと次のようになる。