XOR連結リスト
鍵となるのは、最初の命令と以下のような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 が残されている。
この場合、次のノードのアドレスは、1つ前のノードのアドレスを現在ノードのリンクフィールドの値から減算することで得られる。XOR連結リストとほぼ同じだが、終端ノードのリンクフィールドをゼロにしても反射することはない。なお、加算によってオーバーフローを起こしても何ら問題はない。