XOR Linked List - Why Does IT Work?

Why Does It Work?

The key is the first operation, and the properties of XOR:

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

The R2 register always contains the XOR of the address of current item C with the address of the predecessor item P: C⊕P. The Link fields in the records contain the XOR of the left and right successor addresses, say L⊕R. XOR of R2 (C⊕P) with the current link field (L⊕R) yields C⊕P⊕L⊕R.

• If the predecessor was L, the P(=L) and L cancel out leaving C⊕R.
• If the predecessor had been R, the P(=R) and R cancel, leaving C⊕L.

In each case, the result is the XOR of the current address with the next address. XOR of this with the current address in R1 leaves the next address. R2 is left with the requisite XOR pair of the (now) current address and the predecessor.