/ Coding

The Insider's Guide to XOR Linked List

Introduction

XOR Linked List, also known as Memory-Efficient Linked List, is a form of a doubly linked list that takes less memory than doubly linked list and highly dependent on the XOR logic. Let's understand the basics of XOR Logic and Linked List before diving deeper.

XOR Logic

The XOR Logic is a logical operation that outputs true only when inputs differ.

Input A Input B Result
0 0 0
0 1 1
1 0 1
1 1 0

Linked List

A linked list is a collection of elements, where each item has data and the pointer to the next Item.

408px-Singly-linked-list.svg

Doubly Linked List

A doubly linked list is a linked list with two pointers, pointing to the next and previous nodes. We can traverse the list in two directions forward and backwards.

610px-Doubly-linked-list.svg

Implementation

In an XOR linked list, you store one Pointer per node, which is the XOR of prev and next (or if one of them is absent, just the other (the same as XORing with 0)). The reason why you can still traverse an XOR linked list in both directions relies on the properties of XOR and the redundancy of information inherent in a double linked list.
Imagine you have three nodes in your XOR linked list.

  1. A is the head and has an unobfuscated pointer to B (B XOR 0, next only)
  2. B is the middle element and has the XOR of pointers to A and to C.
  3. C is the tail, and an unobfuscated pointer to B (0 XOR B, prev only)

DoublyLinkedList--1-

Iteration

  1. When we iterate over this list, we start at item A.
  2. We could travel to B using the pointer to B and we note down A's position in memory as we travel to B.
  3. When we wish to travel to C from B we XOR B's pointer with A, granting us the pointer to item C, we could then note B's position in memory and travel to C.
    This works because XOR has the property of undoing itself if applied twice:
    C XOR A XOR A == C

Understanding

Another way to think about it is, the doubly linked list stores no extra information a singly linked list does not (since it's just storing all the previous pointers as copies of next Pointers somewhere else in memory), so by exploiting this redundancy we can have doubly linked list properties with only as many links as are needed. However, This only works if we start our XOR Linked list traversal from the start or end — as if we just jump into a random node in the middle, we do not have the information necessary to start traversing.

Pros and Cons

Pros

  • While an XOR Linked list has the advantage of smaller memory usage

Cons

  • it will confuse the compiler, debugging and static analysis tools as your XOR of two pointers will not be correctly recognised by a Pointer by anything except your code.
  • It also slows down pointer access to have to do the XOR operation to recover the true pointer first.
  • It also can't be used in managed code — XOR obfuscated pointers won't be recognised by the garbage collector.
  • This only works if we start our XOR linked list traversal from the start or end - as if we just jump into a random node in the middle, we do not have the information necessary to start traversing.

References

Linked list
XOR Linked List

The Insider's Guide to XOR Linked List
Share this

Subscribe to Coding Today

Popular queries