Editing XOR linked list (section)

== Description ==
An ordinary doubly linked list stores addresses of the previous and next list items in each list node, requiring two address fields:

  ... A        B        C         D         E ...
          –>  next –>  next  –>  next  –>
          <–  prev <–  prev  <–  prev  <–

An XOR linked list compresses the same information into ''one'' address field by storing the bitwise XOR (here denoted by ⊕) of the address for ''previous'' and the address for ''next'' in one field:

  ... A        B          C          D         E ...
          ⇌   A⊕C   ⇌   B⊕D   ⇌   C⊕E   ⇌

More formally: 
   link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ...

When traversing the list from left to right: supposing the cursor is at C, the previous item, B, may be XORed with the value in the link field (B⊕D). The address for D will then be obtained and list traversal may resume. The same pattern applies in the other direction.

i.e.  {{code|1=addr(D) = link(C) ⊕ addr(B)}}
where
       link(C) = addr(B)⊕addr(D)
so  
       addr(D) = addr(B)⊕addr(D) ⊕ addr(B)           
   
       addr(D) = addr(B)⊕addr(B) ⊕ addr(D) 
since 
        X⊕X = 0                 
        => addr(D) = 0 ⊕ addr(D)
since
        X⊕0 = X
        => addr(D) = addr(D)
The XOR operation cancels {{code|addr(B)}} appearing twice in the equation and all we are left with is the {{code|addr(D)}}.

To start traversing the list in either direction from some point, the address of two consecutive items is required. If the addresses of the two consecutive items are reversed, list traversal will occur in the opposite direction.<ref>{{Cite news|url=https://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/|title=XOR Linked List - A Memory Efficient Doubly Linked List {{!}} Set 1 - GeeksforGeeks|date=2011-05-23|work=GeeksforGeeks|access-date=2018-10-29|language=en-US}}</ref>

===Theory of operation===
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.