XOR Linked List

• A memory efficient doubly linked list.
• An XOR linked list store the bitwise XOR of the address for previous llink and the address for next rlink in one field.
• 利用 XOR 處理這兩個 pointers， 所以

  2 * sizeof (nodePtr) --> sizeof (nodePtr)

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

How to traverse whole linked list?

• We are at node C to find addr(D) :

  addr(B) ⊕ link(C)
  = addr(B) ⊕ (link(B) ⊕ link(D))
  = addr(B) ⊕ link(B) ⊕ link(D)
  = 0 ⊕ link(D)
  = link(D)
  

• While traversing the list you need to remember the address of the previously accessed node in order to calculate the next node's address.

Drawbacks

• Debugging become difficult.
• Hard to maintain. (Decrease in memory usage causes an increase in code complexity)
• The pointers will be unreadable if one isn't traversing the list.

Implementation in C

This is also a drawback that we can't do XOR operation to addresses in C. So we need to do extra type casting.

#include <stdint.h>  // gcc needs this for intptr_t.  

typedef struct xorll {
   int  data;
   struct xorll  *nLink;
}  xorll;

// Creating an xor field
uintptr_t x = (uintptr_t) (void *) prev ^ (uintptr_t) (void *) next;

// Reconstructing an address
prev = (void *) (x ^ (uintptr_t) (void *) next);

• Notice that for platform portability (ex, 32/64 bits), we use uintptr_t instead of unsigned int*.$^{[3]}$

More pratical way

• It is still desirable to reduce the overhead of a linked list.
• Unrolling linked list can not only reduce the memory overhead but can dramatically increase cache performance.

Reference

• [1] Wiki
• [2] GeeksforGeeks, A Memory Efficient Doubly Linked List
• [3] uintptr_t