How to Implement an XOR Linked List in Python

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.

Important limitation in Python

Python's garbage collector uses reference counting. When a node's address is stored only as part of an XOR value (not as a direct reference), Python considers the node unreachable and may garbage-collect it. To prevent this, you must maintain a separate list of all node references. This largely negates the memory savings that make XOR linked lists useful in languages like C or C++.

XOR linked lists in Python are primarily useful for learning and interview preparation, not for production use.

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

Why __nodes is necessary

The __nodes list holds direct references to every node ever created. Without it, Python's garbage collector would destroy nodes whose only references exist as XOR-encoded integers inside other nodes' npx fields. This is the key trade-off of implementing XOR linked lists in a garbage-collected language.

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:
        # Update current head's npx: it now has a previous node
        self.head.npx = id(node) ^ self.head.npx
        # New node's npx: prev is 0, next is current head
        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:
        # Update current tail's npx: it now has a next node
        self.tail.npx = id(node) ^ self.tail.npx
        # New node's npx: prev is current tail, next is 0
        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:
        # Only one node
        res = self.head.value
        self.head = self.tail = None
        return res
    elif (0 ^ self.head.npx) == id(self.tail):
        # Exactly two nodes
        res = self.head.value
        self.head = self.tail
        self.head.npx = self.tail.npx = 0
        return res
    else:
        # More than two nodes
        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:
        # Traverse to the last node
        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
        # Update second-to-last node
        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()

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

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

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

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

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

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

# Updated state
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

When NOT to use XOR linked lists in Python

• Garbage collection conflicts: The __nodes list workaround eliminates the memory savings entirely.
• Debugging difficulty: XOR-encoded pointers are nearly impossible to inspect during debugging.
• No real memory benefit: Python objects have significant overhead (typically 50+ bytes per object), so saving one 8-byte pointer is negligible.
• ctypes.cast is fragile: If a node gets garbage-collected despite the __nodes list (for example, due to a bug), dereferencing its address causes a segmentation fault: a hard crash with no Python traceback.

For production Python code, use a standard doubly linked list or Python's built-in collections.deque.

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.