XOR doubly linked list Implementation

Problem

An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, it holds a field named both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an add(element) which adds the element to the end, and a get(index) which returns the node at index.

If using a language that has no pointers (such as Python), you can assume you have access to get_pointer and dereference_pointer functions that converts between nodes and memory addresses.

What

An XOR Linked List is a variant of the doubly linked list that uses the XOR bitwise operation to reduce the memory usage required for storing pointers.

In traditional double linked list, we use:

A data field.
Two pointers: next (pointing to the next node) and prev (pointing to the previous node).

But in xor linked list, we have:

A data field.
A single pointer named npx (XOR of the next node and the previous node).

So, for a node at position i, npx_i = prev_i ^ next_i, where ^ denotes the XOR bitwise operation.

This npx pointer is both the next AND the previous pointer! How is this possible you might ask?

Well, this is where the XOR comes into play. Lets do a tiny bit of math:

A ^ B = C
=>
C ^ A = B
C ^ B = A

Operations

Creation

While creating the list, we combine the next and previous pointers using XOR, and store the pointer to the first element separately. Let’s denote A as the previous, B as the next, and C as the stored value:

previous ^ next = stored value
stored value ^ previous = next
stored value ^ next = previous

Traversal

Forward

Maintain two pointers: current and prev.
Initialize prev to NULL.
For each node, compute the address of next using the formula next = prev ^ npx.
Update prev to current and current to next.

Backward

This is similar to forward traversal with roles of prev and next swapped.

Pros and Cons

Advantages

Memory Efficiency: Reduces the storage requirement by eliminating one pointer for each node.
Reversibility of section - In a doubly linked list, reversing a section requires swapping all the next and previous pointers. But in xor based linked list, since we combined these pointers using XOR, we don’t need to swap them anymore. This means no changes are necessary

Implementations

Implementation notes

Manipulating Pointers: Though we simulate pointer manipulation using XOR, actual pointer arithmetic is commonly handled using helper methods in higher-level languages like C++.
Handling Edge Cases: Care needs to be taken during insertion and deletion operations to correctly update npx pointers of affected nodes.

C

#include <stdio.h>

#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node * npx; // XOR of next and previous node pointers
}
Node;

// Utility function to XOR two pointers
Node * XOR(Node * a, Node * b) {
    return (Node * )((uintptr_t)(a) ^ (uintptr_t)(b));
}

// Function to add a node at the start
void insert(Node ** head_ref, int data) {
    Node * new_node = (Node * ) malloc(sizeof(Node));
    new_node -> data = data;

    new_node -> npx = * head_ref;

    if ( * head_ref != NULL) {
        ( * head_ref) -> npx = XOR(new_node, ( * head_ref) -> npx);
    }

    * head_ref = new_node;
}

// Function to print nodes in a given XOR linked list
void printList(Node * head) {
    Node * curr = head;
    Node * prev = NULL;
    Node * next;

    while (curr != NULL) {
        printf("%d ", curr -> data);

        next = XOR(prev, curr -> npx);

        prev = curr;
        curr = next;
    }
    printf("\n");
}

int main() {
    Node * head = NULL;

    insert( & head, 10);
    insert( & head, 20);
    insert( & head, 30);
    insert( & head, 40);

    printList(head);

    return 0;
}

C++

#include <iostream>

#include <cstdint> // For uintptr_t

class Node {
    public: int data;
    Node * npx; // XOR of next and previous node pointers
    Node(int val): data(val),
    npx(nullptr) {}
};

// Utility function to XOR two pointers
Node * XOR(Node * a, Node * b) {
    return (Node * )((uintptr_t)(a) ^ (uintptr_t)(b));
}

class XORLinkedList {
    public: XORLinkedList(): head(nullptr) {}

    void add(int data) {
        Node * newNode = new Node(data);
        newNode -> npx = XOR(nullptr, head);

        if (head != nullptr) {
            Node * next = XOR(head -> npx, nullptr);
            head -> npx = XOR(newNode, next);
        }

        head = newNode;
    }

    int get(int index) {
        Node * current = head;
        Node * prev = nullptr;
        Node * next;

        int i;
        for (i = 0; current != nullptr && i < index; i++) {
            next = XOR(prev, current -> npx);
            prev = current;
            current = next;
        }

        if (current != nullptr) {
            return current -> data;
        } else {
            return -1; // Index out of bounds
        }
    }

    private: Node * head;
};

int main() {
    XORLinkedList list;
    list.add(10);
    list.add(20);
    list.add(30);
    list.add(40);

    std::cout << list.get(0) << std::endl; // Output: 40
    std::cout << list.get(1) << std::endl; // Output: 30
    std::cout << list.get(2) << std::endl; // Output: 20
    std::cout << list.get(3) << std::endl; // Output: 10
    std::cout << list.get(4) << std::endl; // Output: -1 (Index out of bounds)

    return 0;
}

Java

Implementing an XOR linked list in Java is quite challenging because Java does not have direct pointer manipulation like C or C++. However, we can simulate this using a Map to store the addresses of the nodes and retrieving them using these simulated addresses.

We can define XorNode:

class XORNode {
	int element;
	int both;
	XORNode(int element) {
		this.element = element;
		this.both = 0;
	}
}

Actual implementation:

import java.util.HashMap;
import java.util.Map;


public class XORLinkedList {

	private XORNode head;

	private XORNode tail;

	private Map<Integer, XORNode> memory;

	private int count; // To simulate memory address allocation
	public XORLinkedList() {
		this.head = null;
		this.tail = null;
		this.memory = new HashMap<>();
		this.count = 1; // To simulate memory addresses starting from 1
	}

	private int getPointer(XORNode node) {
		if (node == null) return 0;
		int address = System.identityHashCode(node);
		memory.put(address, node);
		return address;
	}

	private XORNode dereferencePointer(int address) {
		return memory.get(address);
	}

	public void add(int element) {
		XORNode newNode = new XORNode(element);

		if (head == null) {
			head = newNode;
			tail = newNode;
		} else {
			int newAddress = getPointer(newNode);
			int tailAddress = getPointer(tail);

			newNode.both = tailAddress;
			tail.both = tail.both ^ newAddress;

			tail = newNode;
		}
	}

	public Integer get(int index) {
		int prevAddress = 0;
		int currentAddress = getPointer(head);
		XORNode currentNode = head;

		for (int i = 0; i < index; i++) {
			if (currentNode == null) return null; // Index out of bounds
			int nextAddress = prevAddress ^ currentNode.both;
			prevAddress = currentAddress;
			currentAddress = nextAddress;

			if (currentAddress == 0) return null; // Index out of bounds
			currentNode = dereferencePointer(currentAddress);
		}

		return currentNode != null ? currentNode.element : null;
	}

	public static void main(String[] args) {
		XORLinkedList list = new XORLinkedList();
		list.add(10);
		list.add(20);
		list.add(30);
		list.add(40);

		System.out.println(list.get(0)); // Output: 10
		System.out.println(list.get(1)); // Output: 20
		System.out.println(list.get(2)); // Output: 30
		System.out.println(list.get(3)); // Output: 40
		System.out.println(list.get(4)); // Output: null (Index out of bounds)
	}
}

Problem#

What#

Operations#

Creation#

Traversal#

Forward#

Backward#

Pros and Cons#

Advantages#

Implementations#

Implementation notes#

C#

C++#

Java#