XOR Linked Lists

XOR Linked Lists

https://www.baeldung.com/cs/xor-linked-lists#bd-xor-linked-lists

The idea behind XOR-linked lists is to combine the advantages of both single and double lists. Therefore, we would like to move forward and backwards along the list but without having to store two memory addresses in each item.

Similarly to a single-linked list, the item contains the value, and a single memory address. However, the memory address in XOR-linked lists is the logical XOR operator between the address of the previous and next items in the list.

Traversing the List Forward

When traversing the list forward, it’s important to always keep in hand the memory address of the previous item. Then, we can calculate the address of the next item using the formula:

next = previous XOR current.memoryAddress

Since current.memoryAddress contains the value of previous XOR next, adding the previous value one more time will exclude it from the result. Thus, we get the address of the next item.

Traversing the List Backward

When Traversing the list backwards, we need to keep the address of the next item. To calculate the address of the previous item, we use the following formula:

previous = next XOR current.memoryAddress

Similarly to the previous equation, since current.memoryAddress contains the value of previous ⊕ next, adding the next one more time will exclude it from the result. Thus, we find the address of the previous item.

Advantages and Disadvantages

The main advantage of using XOR-linked lists is that we can move forward and backwards along the list. Thus, we achieve the features of double-linked lists storing only one memory address in each item. As a result, we reduce memory usage while simulating the behaviour of double-linked lists.

Disadvantages of XOR Linked Lists

Use XOR-linked lists only when memory usage is becoming really high, and you don’t mind the additional complexities that come from using them.

Despite its memory-saving advantage, the XOR linked list has significant drawbacks that have prevented it from becoming a mainstream data structure:

1. Debugging Difficulty: Debugging can be extremely challenging because we don’t store the actual addresses anymore inside the item. If an XOR value is corrupted, it can be very difficult to trace the issue.
2. Language Support: Most modern programming languages, including Java, don’t directly support the kind of low-level pointer arithmetic needed for this data structure. In Java, you can’t directly manipulate memory addresses. You would have to use the Unsafe class, which is highly discouraged because it bypasses Java’s memory safety features and can lead to serious bugs and security vulnerabilities.
3. Garbage collection is difficult because we don’t store any proper addresses.
4. Maintenance Overhead: The code for an XOR linked list is more complex and harder to maintain than for a standard doubly linked list because of all the XOR operations needed to calculate the address of the previous and next items. The logic for traversal and insertion is not intuitive.
5. Performance: While saving memory, the need for repeated XOR operations to traverse the list can sometimes be slightly slower than simply following a direct pointer.

In Java

In Java, implementing an XOR linked list directly is not possible due to Java’s memory management model and the lack of low-level pointer arithmetic. Java abstracts away direct memory addresses, managing them with the Garbage Collector. You cannot perform bitwise operations on object references (which are not simple memory addresses), as you can in languages like C or C++.

For all practical purposes in Java, a standard doubly linked list is the correct and safe choice.