XOR Linked List
Exchanging the contents of two variables without using a third is a popular question for the technical interview. But is this property of XOR—namely a ^ b ^ b <=> a—useful outside of interview questions and fun facts to tell at parties? XOR linked lists might be such a use case.
(Java)
import java.util.*;
public class Program {
public static void main(String[] args) {
var testArr = new int[] {1, 2, 3, 4, 5, 10, 3};
System.out.println(Arrays.toString(testArr));
reverseNoTmp(testArr);
System.out.println(Arrays.toString(testArr));
}
public static void reverse(int[] xs) {
for (var i = 0; i < xs.length / 2; i++) {
var swap = xs[i];
xs[i] = xs[xs.length-1-i];
xs[xs.length-1-i] = swap;
}
}
public static void reverseNoTmp(int[] xs) {
for (var i = 0; i < xs.length / 2; i++) {
// a ^ b
xs[i] = xs[i] ^ xs[xs.length-1-i];
// a = (a^b) ^ b
xs[xs.length-1-i] = xs[i] ^ xs[xs.length-1-i];
// b = (a^b) ^ a
xs[i] = xs[i] ^ xs[xs.length-1-i];
}
}
}
Sorry that I made you look at (sidenote: I just happened to have this example lying around. Too lazy to rewrite it now.) code.
It was Leonard Ritter on Mastodon who first made me aware of this technique. Instead of storing the two pointers of a doubly linked list separately, they can be compressed into a single value using XOR.
From xorll.c lines 6 through 9 (C)
typedef struct Xor_Element Xor_Element;
struct Xor_Element {
uintptr_t delta_pointer;
};
In order to traverse such a list we need an iterator to store a pointer to the previous and current nodes.
From xorll.c lines 17 through 21 (C)
typedef struct Xor_Iterator Xor_Iterator;
struct Xor_Iterator {
Xor_Element *prev;
Xor_Element *curr;
};
Then we obtain the next node by the formula next = curr->delta_pointer ^ prev. Remember that the delta pointer stores prev ^ next. So the calculation effectively becomes (prev ^ next) ^ prev <=> next.
From xorll.c lines 84 through 90 (C)
Xor_Element *xor_iterate_next(Xor_Iterator *it) {
Xor_Element *res = it->curr;
Xor_Element *curr = it->curr;
it->curr = (Xor_Element *) (it->curr->delta_pointer ^ (uintptr_t) it->prev);
it->prev = curr;
return res;
}
This approach comes with a few nice advantages. By storing a single (delta) pointer instead of two real pointers we reduce memory usage. Furthermore, because it doesn’t matter whether we do a ^ b ^ b = a or a ^ b ^ a = b, we can easily iterate the list in reverse. Indeed, reversing the linked list reduces to an O(1) operation (time complexity).
From xorll.c lines 71 through 75 (C)
void xor_linked_list_reverse(Xor_Linked_List *list) {
Xor_Element *first = list->first;
list->first = list->last;
list->last = first;
}
Debugging this can become quite hard, since you can’t easily follow pointers anymore. C is also pretty much the only language that allows for this, (sidenote: If all the GC does is scan the stack and heap for words that look like pointers.) can’t recognize delta pointers. If all you have is a node, you can’t get to its previous or next element. Neither can you insert before or after. Instead you need an iterator like defined in a previous section.
You’ll have a better learning experience if you first give it a go at implementing XOR-ed linked lists yourself. I suggest the following interface:
(C)
struct Xor_Element {
uintptr_t link;
};
struct Xor_Linked_List {
Xor_Element *first;
Xor_Element *last;
};
struct Xor_Iterator {
Xor_Element *prev;
Xor_Element *curr;
};
void xorll_push_back(Xor_Linked_List *list, Xor_Element *element);
void xorll_push_front(Xor_Linked_List *list, Xor_Element *element);
Xor_Element *xorll_pop_back(Xor_Linked_List *list);
Xor_Element *xorll_pop_front(Xor_Linked_List *list);
void xorll_reverse(Xor_Linked_List *list);
// Iterator will be setup to point to the first node in the list.
// Call `xorll_iterator_next` to get the first node and advance the iterator.
Xor_Iterator xorll_get_iterator(Xor_Linked_List list);
Xor_Element *xorll_iterator_next(Xor_Iterator *it);
// Insert `element` after the current element in the iterator.
// Subsequently calling `xorll_iterator_next` will return the just inserted element.
void xorll_iterator_insert(Xor_Iterator *it, Xor_Element *element);
// Remove the current element (i.e., the element that was returned by the last `xorll_iterator_next` call).
void xorll_iterator_remove(Xor_Iterator *it);
Here is a complete (sidenote: The naming is a bit different. This is my first implementation and I was more concerned with implementation details, than with good naming.) that supports iterating and adding and removing elements from front or back.
From xorll.c lines 1 through 104 (C)
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
typedef struct Xor_Element Xor_Element;
struct Xor_Element {
uintptr_t delta_pointer;
};
typedef struct Xor_Linked_List Xor_Linked_List;
struct Xor_Linked_List {
Xor_Element *first;
Xor_Element *last;
};
typedef struct Xor_Iterator Xor_Iterator;
struct Xor_Iterator {
Xor_Element *prev;
Xor_Element *next;
};
void xor_linked_list_append(Xor_Linked_List *list, Xor_Element *element) {
if (list->last == NULL) {
assert(list->first == NULL && "If last is null, first should also be null");
list->last = list->first = element;
} else {
assert(list->first && "If last is not null, first should also be not null");
element->delta_pointer = (uintptr_t) list->last /* ^ NULL */;
list->last->delta_pointer = list->last->delta_pointer ^ (uintptr_t) element;
list->last = element;
}
}
Xor_Element *xor_linked_list_pop_back(Xor_Linked_List *list) {
Xor_Element *res = list->last;
if (list->last == list->first) {
list->last = list->first = NULL;
} else {
Xor_Element *second_to_last = (Xor_Element *) list->last->delta_pointer /* ^ NULL */;
second_to_last->delta_pointer = second_to_last->delta_pointer ^ (uintptr_t) list->last;
list->last = second_to_last;
}
return res;
}
void xor_linked_list_push(Xor_Linked_List *list, Xor_Element *element) {
if (list->first == NULL) {
assert(list->last == NULL && "If first is null, last should also be null");
list->first = list->last = element /* ^ NULL */;
} else {
assert(list->last && "If first is not null, last should also be not null");
element->delta_pointer = (uintptr_t) list->first;
list->first->delta_pointer = list->first->delta_pointer ^ (uintptr_t) element;
list->first = element;
}
}
Xor_Element *xor_linked_list_pop_front(Xor_Linked_List *list) {
Xor_Element *res = list->first;
if (list->first == list->last) {
list->first = list->last = NULL;
} else {
Xor_Element *second = (Xor_Element *) list->first->delta_pointer /* ^ NULL */;
second->delta_pointer = second->delta_pointer ^ (uintptr_t) list->first;
list->first = second;
}
return res;
}
void xor_linked_list_reverse(Xor_Linked_List *list) {
Xor_Element *first = list->first;
list->first = list->last;
list->last = first;
}
Xor_Iterator xor_linked_list_iterate(Xor_Linked_List list) {
return (Xor_Iterator) {
.prev = NULL,
.next = list.first,
};
}
Xor_Element *xor_iterate_next(Xor_Iterator *it) {
Xor_Element *res = it->next;
Xor_Element *cur = it->next;
it->next = (Xor_Element *) (it->next->delta_pointer ^ (uintptr_t) it->prev);
it->prev = cur;
return res;
}
void xor_iterate_insert(Xor_Iterator *it, Xor_Element *element) {
element->delta_pointer = (uintptr_t) it->prev ^ (uintptr_t) it->next;
it->prev->delta_pointer = it->prev->delta_pointer ^ (uintptr_t) it->next ^ (uintptr_t) element;
it->next->delta_pointer = it->next->delta_pointer ^ (uintptr_t) it->prev ^ (uintptr_t) element;
it->next = element;
}
void xor_iterato_remove(Xor_Iterator *it) {
Xor_Element *prev_prev = (Xor_Element *) (it->prev->delta_pointer ^ (uintptr_t) it->next);
prev_prev->delta_pointer = prev_prev->delta_pointer ^ (uintptr_t) it->prev ^ (uintptr_t) it->next;
it->next->delta_pointer = it->next->delta_pointer ^ (uintptr_t) it->prev ^ (uintptr_t) prev_prev;
it->prev = prev_prev;
}
You might use it like this:
From xorll.c lines 107 through 191 (C)
typedef struct Node Node;
struct Node {
Xor_Element list; // embed linked list, must be the first field to allow treating `Node`s as `Xor_Element`s
int val;
};
int main(void) {
Xor_Linked_List list = {0};
for (int i = 0; i < 10; ++i) {
Node *node = calloc(1, sizeof(Node));
assert(node != NULL);
node->val = i;
if (i % 2 == 0) {
xor_linked_list_append(&list, (Xor_Element *) node);
} else {
xor_linked_list_push(&list, (Xor_Element *) node);
}
}
{ // insert 99 in the middle of the list and then remove it again
Xor_Iterator it = xor_linked_list_iterate(list);
for (int i = 0; i < 5; ++i) {
xor_iterate_next(&it);
}
Node *node = calloc(1, sizeof(Node));
node->val = 99;
xor_iterate_insert(&it, (Xor_Element *) node);
Node *next = (Node *) xor_iterate_next(&it);
assert(next == node);
xor_iterato_remove(&it);
assert(((Node *)it.prev)->val == 1);
}
{ // iterate through the list and print it out
Xor_Iterator it = xor_linked_list_iterate(list);
while (it.next) {
Node *node = (Node *) xor_iterate_next(&it);
printf("%d\n", node->val);
}
}
printf("-----------------------------------------------\n");
{ // reverse the list in O(1) and iterate through it, printing out each element
xor_linked_list_reverse(&list); // O(1)
Xor_Iterator it = xor_linked_list_iterate(list);
while (it.next) {
Node *node = (Node *) xor_iterate_next(&it);
printf("%d\n", node->val);
}
}
printf("-----------------------------------------------\n");
{ // remove an element from the front
xor_linked_list_pop_front(&list);
Xor_Iterator it = xor_linked_list_iterate(list);
while (it.next) {
Node *node = (Node *) xor_iterate_next(&it);
printf("%d\n", node->val);
}
}
printf("-----------------------------------------------\n");
{ // remove an element from the back
xor_linked_list_pop_back(&list);
Xor_Iterator it = xor_linked_list_iterate(list);
while (it.next) {
Node *node = (Node *) xor_iterate_next(&it);
printf("%d\n", node->val);
}
}
return 0;
}
Free? Nah, I’ll leave that to the exit syscall.
Relevant articles
2024-03-22, by Wikipedia
In computer programming, the exclusive or swap (sometimes shortened to XOR swap) is an algorithm that uses the exclusive or bitwise operation to swap the values of two variables without using the temporary variable which is normally required.
2024-05-26, by Wikipedia
An XOR linked list is a type of data structure used in computer programming. It takes advantage of the bitwise XOR operation to decrease storage requirements for doubly linked lists by storing the composition of both addresses in one field. While the composed address is not meaningful on its own, during traversal it can be combined with knowledge of the last-visited node address to deduce the address of the following node.
2024-06-08, by paniq
Doubly linked list with delta pointers: p[x] = { value, xor(p[x-1], p[x+1]) } Then, starting at p[-1] = null, p[0] = p_first: p[n+1] = xor(p[n][1], p[n-1]) To go backwards, exchange p_first with p_last in the above formula.