XOR Linked List

An ordinary doubly linked list requires space for two address field to store the addressed of previous and next node. Now address can be represented into XOR operation of next and previous address, which called NPX.

In the XOR linked link^[1], instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes. While traversing the list we need to remember the address of the previously accessed node in order to calculate the next node's address.

Basic concept (XOR itself and XOR associative) behind it:

Node A:
	npx = 0 XOR addr(B) // bitwise XOR of zero and address of B
Node B:
	npx = addr(A) XOR addr(C) // bitwise XOR of address of A and address of C
Node C:
	npx = addr(B) XOR addr(D) // bitwise XOR of address of B and address of D
Node D:
	npx = addr(C) XOR 0 // bitwise XOR of address of C and 0

Thus, if a want to get address of D, I can XOR npx of C and addr B.

npx(C) XOR addr(B)
=> (addr(B) XOR addr(D)) XOR addr(B) // npx(C) = addr(B) XOR addr(D)
=> addr(B) XOR addr(D) XOR addr (B) 
=> addr(D) XOR 0 // a ^ a = 0
=> addr(D) // a ^ 0 = a