[mananaysiempre]

> storing the difference [of prev and next pointers] would require an extra [sign] bit [relative to XOR]

No it wouldn’t. Just let wraparound happen normally and things will work out.

Effectively what you need are functions

  pair  : ptr × ptr → uintptr
  left  : uintptr × ptr → ptr
  right : ptr × uintptr → ptr
  
  left(pair(x, y), y) ≡ x
  right(x, pair(x, y)) ≡ y

Setting all three to XOR is one possibility. But

  pair(x, y)  = (x + y) mod 2^(width of ptr)
  left(p, y)  = (p - y) mod 2^(width of ptr)
  right(x, p) = (p - x) mod 2^(width of ptr)

is an equally valid one, because addition and subtraction modulo any fixed value are related in exactly the same way as normal addition and subtraction.