How to Implement an XOR Linked List in Python

Learn how to create a memory-efficient XOR linked list in Python using bitwise operations and ctypes, including implementation details, caveats, and performance trade-offs.

An XOR Linked List (also called a Memory-Efficient Doubly Linked List) is a clever variation of a standard doubly linked list that uses only one pointer per node instead of two. In a regular doubly linked list, each node stores separate prev and next pointers. An XOR linked list replaces both with a single field that stores the XOR of the previous and next node addresses, cutting the pointer overhead in half.

This data structure is a classic example of using bitwise operations to optimize memory usage and is a popular topic in advanced data structures courses and technical interviews.

In this guide, you will learn how an XOR linked list works, how to implement one in Python using the ctypes module, and what critical caveats you need to be aware of when using this approach in Python.

How XOR Linked Lists Work

In a standard doubly linked list, each node stores:

prev → address of the previous node
next → address of the next node

In an XOR linked list, each node stores only:

npx → address(prev) XOR address(next)

To traverse the list, you need to know the address of one adjacent node. Since XOR is its own inverse, you can recover the other address:

next_address = prev_address XOR npx
prev_address = next_address XOR npx

This is possible because of the XOR property: A XOR B XOR A = B.

Example traversal from head:

At the head node, prev is 0 (there is no previous node).
next_address = 0 XOR head.npx → gives the address of the second node.
At the second node, next_address = address(head) XOR second.npx → gives the third node, and so on.

Building the Node Class

Each node stores a value and an npx field (the XOR of previous and next node addresses):

class Node:
    def __init__(self, value):
        self.value = value
        self.npx = 0  # XOR of prev and next node addresses

When a node is first created, npx is 0 because it has no neighbors yet.

Building the XOR Linked List Class

The XorLinkedList class manages the nodes and provides all standard doubly linked list operations. It uses Python's ctypes module to convert integer memory addresses back into Python object references.

Initialization and the Type Cast Helper

import ctypes


class XorLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.__nodes = []  # Prevents garbage collection of nodes

    def __type_cast(self, id):
        """Convert a memory address (int) back to a Python object reference."""
        return ctypes.cast(id, ctypes.py_object).value

Insert at Start

Adds a new node at the beginning of the list:

def InsertAtStart(self, value):
    node = Node(value)
    if self.head is None:
        self.head = node
        self.tail = node
    else:
        self.head.npx = id(node) ^ self.head.npx
        node.npx = id(self.head)
        self.head = node
    self.__nodes.append(node)

Insert at End

Adds a new node at the end of the list:

def InsertAtEnd(self, value):
    node = Node(value)
    if self.head is None:
        self.head = node
        self.tail = node
    else:
        self.tail.npx = id(node) ^ self.tail.npx
        node.npx = id(self.tail)
        self.tail = node
    self.__nodes.append(node)

Delete at Start

Removes the first node from the list:

def DeleteAtStart(self):
    if self.isEmpty():
        return "List is empty!"
    elif self.head == self.tail:
        res = self.head.value
        self.head = self.tail = None
        return res
    elif (0 ^ self.head.npx) == id(self.tail):
        res = self.head.value
        self.head = self.tail
        self.head.npx = self.tail.npx = 0
        return res
    else:
        res = self.head.value
        next_node = self.__type_cast(0 ^ self.head.npx)
        next_next_id = id(self.head) ^ next_node.npx
        self.head = next_node
        self.head.npx = 0 ^ next_next_id
        return res

Delete at End

Removes the last node from the list:

def DeleteAtEnd(self):
    if self.isEmpty():
        return "List is empty!"
    elif self.head == self.tail:
        res = self.tail.value
        self.head = self.tail = None
        return res
    elif self.__type_cast(0 ^ self.head.npx) == self.tail:
        res = self.tail.value
        self.tail = self.head
        self.head.npx = self.tail.npx = 0
        return res
    else:
        prev_id = 0
        node = self.head
        next_id = 1
        while next_id:
            next_id = prev_id ^ node.npx
            if next_id:
                prev_id = id(node)
                node = self.__type_cast(next_id)
        res = node.value
        second_last = self.__type_cast(prev_id)
        new_npx = second_last.npx ^ id(node)
        second_last.npx = new_npx ^ 0
        self.tail = second_last
        return res

Forward Traversal

Traverses the list from head to tail:

def Print(self):
    if self.head is not None:
        prev_id = 0
        node = self.head
        next_id = 1
        print(node.value, end=' ')
        while next_id:
            next_id = prev_id ^ node.npx
            if next_id:
                prev_id = id(node)
                node = self.__type_cast(next_id)
                print(node.value, end=' ')
            else:
                return
    else:
        print("List is empty!")

Reverse Traversal

Traverses the list from tail to head: one of the key advantages of a doubly linked list.

def ReversePrint(self):
    if self.head is not None:
        prev_id = 0
        node = self.tail
        next_id = 1
        print(node.value, end=' ')
        while next_id:
            next_id = prev_id ^ node.npx
            if next_id:
                prev_id = id(node)
                node = self.__type_cast(next_id)
                print(node.value, end=' ')
            else:
                return
    else:
        print("List is empty!")

Utility Methods

def Length(self):
    """Return the number of nodes in the list."""
    if not self.isEmpty():
        prev_id = 0
        node = self.head
        next_id = 1
        count = 1
        while next_id:
            next_id = prev_id ^ node.npx
            if next_id:
                prev_id = id(node)
                node = self.__type_cast(next_id)
                count += 1
            else:
                return count
    else:
        return 0

def PrintByIndex(self, index):
    """Return the value at a given index."""
    prev_id = 0
    node = self.head
    for i in range(index):
        next_id = prev_id ^ node.npx
        if next_id:
            prev_id = id(node)
            node = self.__type_cast(next_id)
        else:
            return "Index out of range."
    return node.value

def isEmpty(self):
    """Return True if the list has no nodes."""
    return self.head is None

Complete Implementation

Here is the full, consolidated code:

import ctypes


class Node:
    def __init__(self, value):
        self.value = value
        self.npx = 0


class XorLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.__nodes = []

    def __type_cast(self, id):
        return ctypes.cast(id, ctypes.py_object).value

    def InsertAtStart(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.head.npx = id(node) ^ self.head.npx
            node.npx = id(self.head)
            self.head = node
        self.__nodes.append(node)

    def InsertAtEnd(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.npx = id(node) ^ self.tail.npx
            node.npx = id(self.tail)
            self.tail = node
        self.__nodes.append(node)

    def DeleteAtStart(self):
        if self.isEmpty():
            return "List is empty!"
        elif self.head == self.tail:
            res = self.head.value
            self.head = self.tail = None
            return res
        elif (0 ^ self.head.npx) == id(self.tail):
            res = self.head.value
            self.head = self.tail
            self.head.npx = self.tail.npx = 0
            return res
        else:
            res = self.head.value
            next_node = self.__type_cast(0 ^ self.head.npx)
            next_next_id = id(self.head) ^ next_node.npx
            self.head = next_node
            self.head.npx = 0 ^ next_next_id
            return res

    def DeleteAtEnd(self):
        if self.isEmpty():
            return "List is empty!"
        elif self.head == self.tail:
            res = self.tail.value
            self.head = self.tail = None
            return res
        elif self.__type_cast(0 ^ self.head.npx) == self.tail:
            res = self.tail.value
            self.tail = self.head
            self.head.npx = self.tail.npx = 0
            return res
        else:
            prev_id = 0
            node = self.head
            next_id = 1
            while next_id:
                next_id = prev_id ^ node.npx
                if next_id:
                    prev_id = id(node)
                    node = self.__type_cast(next_id)
            res = node.value
            second_last = self.__type_cast(prev_id)
            new_npx = second_last.npx ^ id(node)
            second_last.npx = new_npx ^ 0
            self.tail = second_last
            return res

    def Print(self):
        if self.head is not None:
            prev_id = 0
            node = self.head
            next_id = 1
            print(node.value, end=' ')
            while next_id:
                next_id = prev_id ^ node.npx
                if next_id:
                    prev_id = id(node)
                    node = self.__type_cast(next_id)
                    print(node.value, end=' ')
                else:
                    return
        else:
            print("List is empty!")

    def ReversePrint(self):
        if self.head is not None:
            prev_id = 0
            node = self.tail
            next_id = 1
            print(node.value, end=' ')
            while next_id:
                next_id = prev_id ^ node.npx
                if next_id:
                    prev_id = id(node)
                    node = self.__type_cast(next_id)
                    print(node.value, end=' ')
                else:
                    return
        else:
            print("List is empty!")

    def Length(self):
        if not self.isEmpty():
            prev_id = 0
            node = self.head
            next_id = 1
            count = 1
            while next_id:
                next_id = prev_id ^ node.npx
                if next_id:
                    prev_id = id(node)
                    node = self.__type_cast(next_id)
                    count += 1
                else:
                    return count
        else:
            return 0

    def PrintByIndex(self, index):
        prev_id = 0
        node = self.head
        for i in range(index):
            next_id = prev_id ^ node.npx
            if next_id:
                prev_id = id(node)
                node = self.__type_cast(next_id)
            else:
                return "Index out of range."
        return node.value

    def isEmpty(self):
        return self.head is None

Example Usage and Output

obj = XorLinkedList()

obj.InsertAtEnd(2)
obj.InsertAtEnd(3)
obj.InsertAtEnd(4)
obj.InsertAtStart(0)
obj.InsertAtStart(6)
obj.InsertAtEnd(55)

print("Length:", obj.Length())

print("\nTraverse linked list:")
obj.Print()

print("\n\nTraverse in reverse order:")
obj.ReversePrint()

print("\n\nNodes:")
for i in range(obj.Length()):
    print(f"  Index {i}: {obj.PrintByIndex(i)}")

print("\nDelete last node:", obj.DeleteAtEnd())
print("Delete first node:", obj.DeleteAtStart())

print("\nUpdated length:", obj.Length())

print("\nNodes:")
for i in range(obj.Length()):
    print(f"  Index {i}: {obj.PrintByIndex(i)}")

print("\nTraverse linked list:")
obj.Print()

print("\n\nTraverse in reverse order:")
obj.ReversePrint()

Output:

Length: 6

Traverse linked list:
6 0 2 3 4 55 

Traverse in reverse order:
55 4 3 2 0 6 

Nodes:
  Index 0: 6
  Index 1: 0
  Index 2: 2
  Index 3: 3
  Index 4: 4
  Index 5: 55

Delete last node: 55
Delete first node: 6

Updated length: 4

Nodes:
  Index 0: 0
  Index 1: 2
  Index 2: 3
  Index 3: 4

Traverse linked list:
0 2 3 4 

Traverse in reverse order:
4 3 2 0

Time and Space Complexity

Operation	Time Complexity	Explanation
InsertAtStart	O(1)	Direct pointer manipulation at the head
InsertAtEnd	O(1)	Direct pointer manipulation at the tail
DeleteAtStart	O(1)	Only updates head and its neighbor
DeleteAtEnd	O(n)	Must traverse the entire list to find the second-to-last node
Print / ReversePrint	O(n)	Visits every node once
Length	O(n)	Traverses the entire list to count nodes
PrintByIndex	O(n)	Traverses up to `index` nodes

Space Complexity: O(n) for the __nodes list that prevents garbage collection, plus O(n) for the nodes themselves.

XOR Linked List vs. Standard Doubly Linked List

Aspect	XOR Linked List	Standard Doubly Linked List
Pointers per node	1 (`npx`)	2 (`prev` + `next`)
Memory per node	Lower (in C/C++)	Higher
Traversal	Bidirectional ✅	Bidirectional ✅
Implementation complexity	High	Low
Python compatibility	Poor (requires `ctypes` hack)	Excellent
Practical use in Python	Learning only	Production-ready

Conclusion

The XOR linked list is an elegant data structure that achieves bidirectional traversal with only one pointer per node by leveraging the mathematical properties of the XOR operation.

While it provides genuine memory savings in low-level languages like C and C++, its Python implementation requires workarounds (ctypes and a reference-holding list) that negate the benefits.

Nonetheless, understanding XOR linked lists is valuable for deepening your knowledge of bitwise operations, pointer manipulation, and memory-efficient data structures: all of which are common topics in advanced interviews and systems programming.