Editing XOR linked list (section)

==Variations==
The underlying principle of the XOR linked list can be applied to any reversible binary operation. Replacing XOR by addition or subtraction gives slightly different, but largely equivalent, formulations:

===Addition linked list===

  ...  A        B         C         D         E  ...
           ⇌   A+C   ⇌   B+D   ⇌   C+E   ⇌

This kind of list has exactly the same properties as the XOR linked list, except that a zero link field is not a "mirror". The address of the next node in the list is given by subtracting the previous node's address from the current node's link field.

===Subtraction linked list===

  ...  A        B         C         D         E  ...
           ⇌   C-A   ⇌   D-B   ⇌   E-C   ⇌

This kind of list differs from the standard "traditional" XOR linked list in that the instruction sequences needed to traverse the list forwards is different from the sequence needed to traverse the list in reverse. The address of the next node, going forwards, is given by ''adding'' the link field to the previous node's address; the address of the preceding node is given by ''subtracting'' the link field from the next node's address.

The subtraction linked list is also special in that the entire list can be relocated in memory without needing any patching of pointer values, since adding a constant offset to each address in the list will not require any changes to the values stored in the link fields. (See also [[serialization]].) This is an advantage over both XOR linked lists and traditional linked lists.

===Binary search tree===
The XOR linked list concept can be generalized to XOR [[binary search tree]]s.<ref>{{cite web |url=https://github.com/user1095108/xsg |title=c++ associative containers based on the XOR scapegoat tree |website=[[GitHub]] |access-date=5 November 2021}}</ref>