How exactly does the XOR Linked list work?

Question

Below is the link.
The implementation is said to work by storing the XOR of the previous and next addresses (say nxp), instead of storing both (previous and next address) separately. However, later in the implementation, they say that xor-ing the previous address and nxp work to get the next address.

But doesn't this really use the same space as the previous and next pointers?

Answer 1

In a doubly linked list, you save two pointers to node: prev and next. In the linked XOR list, you save one "pointer" to the node, which is the XOR of the previous and next (or if one of them is absent, then the other (the same as XORing with 0)). The reason you can still cross the XOR linked list in both directions depends on the XOR properties and the redundancy of information inherent in the double linked list.

---

Imagine you have three nodes in your linked XOR list.

A is the head, and it has a straightforward pointer to B (B XOR 0, only the following)

B is the middle element and has XOR pointers to A and C.

C is the tail, not a confusing pointer to B (only 0 XOR B, only prev)

When I repeat this list, I start with A. I mark the position in memory when I switch to B. When I want to go to C, I have an XOR B pointer from A, giving me a pointer to C. Then I mark B in memory and move to C.

This works because XOR has the ability to destroy itself if applied twice: C XOR A XOR A == C. Another way to think about this is that a doubly linked list does not contain additional information that is not in a separate list (since since it simply stores all previous pointers in the form of copies of the following pointers somewhere else in memory), therefore, using this redundancy, we can have double-linked properties containing only as many references as necessary. However . This only works if we start traversing the linked XOR list from the beginning or the end - as if we just go to a random node in the middle, we don’t have the information needed to start the move.

---

While a linked XOR list has the advantage of using less memory, it has drawbacks - it will confuse the compiler, debugging and static analysis tools, since your two-pointer XOR will not be correctly recognized by the pointer by anything other than your code.This also slows down pointer access to perform an XOR operation to first restore the true pointer. It also cannot be used in managed code. XOR tangled objects will not be recognized by the garbage collector.

Answer 2

A double linked list requires 2 * N pointers stored for N nodes, plus at least one additional pointer (head, or possibly head and tail).

A linked XOR list requires N pointers stored for N nodes, plus at least two additional pointers (start and last visited node, or possibly head and tail and last visited node). When moving, you save one node (the last node visited), but when you go to the next node, you rewrite it with the previous node address.

Answer 3

But is it practically not used in the same space as the previous and next pointers?

No - it uses about half the space, as the size of the XOR-ing result "prev" and "next" is equal to the size of the larger of the two.

Answer 4

XOR has a very special property, namely, given a XOR b = c , to calculate the third one, only two (any two) variables are required with some restrictions. See the XOR sharing algorithm for why this works.

In this case, the previous (or next) pointer should still be carried forward, but only through traversal calculations, and not as a separate element.