Basic Operations of XOR Linked list
- Insertion
- Deletion
Insertion at Beginning in XOR Linked List:
Below is the steps for insert an element at beginning in XOR Linked List:
- Create a new node , initialize the data and address to the (NULL ^ address of head)
- Then check, If the list is empty, return with that node;
- Otherwise, assign the XOR of the head node to the XOR(new_node address, XOR(head->both, nullptr))
Insertion at end in XOR Linked List:
Below is the steps for insert an element at end in XOR Linked List:
- Create a new node , initialize the data and address to the (NULL ^ add. of tail)
- Then check, If the list is empty, return with that node;
- Otherwise, assign the XOR of the tail node to the XOR(XOR(tail->both, nullptr), new_node address)
Deletion at Beginning in XOR Linked List:
Below is the steps for delete an element at beginning in XOR Linked List:
- Check if the head pointer is not null (i.e., the list is not empty).
- Find the next node’s address using XOR by performing XOR(head->both, nullptr)
- Delete the current head node to free up the memory.and Update the head pointer to point to the calculated next node.
Deletion at End in XOR Linked List:
Below is the steps for delete an element at beginning in XOR Linked List:
- Check if the tail pointer is not null (i.e., the list is not empty).
- If the list is not empty:
- Find the previous node’s address using XOR by performing XOR(tail->both, nullptr). This gives you the previous node in the list.
- Delete the current tail node to free up the memory.
- Update the tail pointer to point to the calculated previous node.
Below is the implementation of the above approach:
// for uintptr_t
#include <cstdint>
#include <iostream>
struct Node {
int data;
// XOR of next and prev
Node* both;
};
class XORLinkedList {
private:
Node* head;
Node* tail;
// XOR function for Node pointers
Node* XOR(Node* a, Node* b);
public:
// Constructor to initialize an empty
// list
XORLinkedList();
// Insert a node at the head of the list
void insert_at_head(int data);
// Insert a node at the tail of the list
void insert_at_tail(int data);
// Delete a node from the head
// of the list
void delete_from_head();
// Delete a node from the tail
// of the list
void delete_from_tail();
// Print the elements of the list
void print_list();
};
XORLinkedList::XORLinkedList()
{
head = tail = nullptr; // Initialize head and tail to
// nullptr for an empty list
}
Node* XORLinkedList::XOR(Node* a, Node* b)
{
return (
// XOR operation for Node pointers
Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}
void XORLinkedList::insert_at_head(int data)
{
Node* new_node = new Node();
new_node->data = data;
new_node->both = XOR(nullptr, head);
if (head) {
head->both
= XOR(new_node, XOR(head->both, nullptr));
}
else {
// If the list was empty, the new
// node is both the head and the
// tail
tail = new_node;
}
// Update the head to the new node
head = new_node;
}
void XORLinkedList::insert_at_tail(int data)
{
Node* new_node = new Node();
new_node->data = data;
new_node->both = XOR(tail, nullptr);
if (tail) {
tail->both
= XOR(XOR(tail->both, nullptr), new_node);
}
else {
// If the list was empty, the new
// node is both the head and the
// tail
head = new_node;
}
// Update the tail to the new node
tail = new_node;
}
void XORLinkedList::delete_from_head()
{
if (head) {
Node* next = XOR(head->both, nullptr);
delete head;
head = next;
if (next) {
next->both = XOR(next->both, head);
}
else {
// If the list becomes empty,
// update the tail to nullptr
tail = nullptr;
}
}
}
void XORLinkedList::delete_from_tail()
{
if (tail) {
Node* prev = XOR(tail->both, nullptr);
delete tail;
tail = prev;
if (prev) {
prev->both = XOR(prev->both, tail);
}
else {
// If the list becomes empty, update the head to
// nullptr
head = nullptr;
}
}
}
void XORLinkedList::print_list()
{
Node* current = head;
Node* prev = nullptr;
while (current) {
std::cout << current->data << " ";
Node* next = XOR(prev, current->both);
prev = current;
current = next;
}
std::cout << std::endl;
}
int main()
{
XORLinkedList list;
list.insert_at_head(10);
list.insert_at_head(20);
list.insert_at_tail(30);
list.insert_at_tail(40);
// prints 20 10 30 40
list.print_list();
list.delete_from_head();
// prints 10 30 40
list.print_list();
list.delete_from_tail();
// prints 10 30
list.print_list();
return 0;
}
import java.util.HashMap;
class Node {
int data;
int both; // This will hold the XOR of the next and previous node IDs
public Node(int data) {
this.data = data;
this.both = 0;
}
}
class XORLinkedList {
private Node head;
private Node tail;
// HashMap to store Node objects by their IDs. This is necessary because Java doesn't
// provide direct access to objects based on memory location.
private HashMap<Integer, Node> nodes;
public XORLinkedList() {
this.head = this.tail = null;
this.nodes = new HashMap<>();
}
private int _xor(int a, int b) {
// Helper function to get the XOR of two IDs
return a ^ b;
}
public void insertAtHead(int data) {
// Inserts a new node with the provided data at the head of the list
Node newNode = new Node(data);
int newId = System.identityHashCode(newNode);
nodes.put(newId, newNode);
if (head != null) {
// Adjusting both values for the new node and existing head
newNode.both = _xor(0, System.identityHashCode(head));
head.both = _xor(newNode.both, System.identityHashCode(head));
} else {
// If the list is empty, the new node becomes the tail
tail = newNode;
}
head = newNode;
}
public void insertAtTail(int data) {
// Inserts a new node with the provided data at the tail of the list
Node newNode = new Node(data);
int newId = System.identityHashCode(newNode);
nodes.put(newId, newNode);
if (tail != null) {
// Adjusting both values for the new node and existing tail
newNode.both = _xor(System.identityHashCode(tail), 0);
tail.both = _xor(newNode.both, System.identityHashCode(tail));
} else {
// If the list is empty, the new node becomes the head
head = newNode;
}
tail = newNode;
}
public void deleteFromHead() {
// Deletes the head node from the list
if (head != null) {
// If there's a next node after the head, update its both value
int nextNodeId = _xor(0, head.both);
Node nextNode = nodes.getOrDefault(nextNodeId, null);
if (nextNode != null) {
nextNode.both = _xor(System.identityHashCode(head), nextNode.both);
} else {
tail = null;
}
// Remove the current head from the nodes HashMap and update the head pointer
nodes.remove(System.identityHashCode(head));
head = nextNode;
}
}
public void deleteFromTail() {
// Deletes the tail node from the list
if (tail != null) {
// If there's a previous node before the tail, update its both value
int prevNodeId = _xor(tail.both, 0);
Node prevNode = nodes.getOrDefault(prevNodeId, null);
if (prevNode != null) {
prevNode.both = _xor(System.identityHashCode(tail), prevNode.both);
} else {
head = null;
}
// Remove the current tail from the nodes HashMap and update the tail pointer
nodes.remove(System.identityHashCode(tail));
tail = prevNode;
}
}
public void printList() {
// Prints the entire list from head to tail
Node current = head;
int prevId = 0;
while (current != null) {
System.out.print(current.data + " ");
// Compute the ID of the next node
int nextId = _xor(prevId, current.both);
// Move the pointers
prevId = System.identityHashCode(current);
current = nodes.getOrDefault(nextId, null);
}
System.out.println();
}
public static void main(String[] args) {
XORLinkedList list = new XORLinkedList();
list.insertAtHead(10);
list.insertAtHead(20);
list.insertAtTail(30);
list.insertAtTail(40);
list.printList(); // Expected: 20 10 30 40
list.deleteFromHead();
list.printList(); // Expected: 10 30 40
list.deleteFromTail();
list.printList(); // Expected: 10 30
}
}
class Node:
def __init__(self, data):
self.data = data
self.both = 0 # This will hold the XOR of the next and previous node IDs
class XORLinkedList:
def __init__(self):
self.head = self.tail = None
# Dictionary to store Node objects by their IDs. This is necessary because Python doesn't
# provide direct access to objects based on memory location.
self.nodes = {}
def _xor(self, a, b):
"""Helper function to get the XOR of two IDs."""
return a ^ b
def insert_at_head(self, data):
"""Inserts a new node with the provided data at the head of the list."""
new_node = Node(data)
new_id = id(new_node)
self.nodes[new_id] = new_node
if self.head:
# Adjusting both values for new node and existing head
new_node.both = self._xor(0, id(self.head))
self.head.both = self._xor(new_node.both, id(self.head))
else:
# If list is empty, the new node becomes the tail
self.tail = new_node
self.head = new_node
def insert_at_tail(self, data):
"""Inserts a new node with the provided data at the tail of the list."""
new_node = Node(data)
new_id = id(new_node)
self.nodes[new_id] = new_node
if self.tail:
# Adjusting both values for new node and existing tail
new_node.both = self._xor(id(self.tail), 0)
self.tail.both = self._xor(new_node.both, id(self.tail))
else:
# If list is empty, the new node becomes the head
self.head = new_node
self.tail = new_node
def delete_from_head(self):
"""Deletes the head node from the list."""
if self.head:
# If there's a next node after the head, update its both value
next_node_id = self._xor(0, self.head.both)
next_node = self.nodes.get(next_node_id) if next_node_id else None
if next_node:
next_node.both = self._xor(id(self.head), next_node.both)
else:
self.tail = None
# Remove the current head from the nodes dictionary and update the head pointer
del self.nodes[id(self.head)]
self.head = next_node
def delete_from_tail(self):
"""Deletes the tail node from the list."""
if self.tail:
# If there's a previous node before the tail, update its both value
prev_node_id = self._xor(self.tail.both, 0)
prev_node = self.nodes.get(prev_node_id) if prev_node_id else None
if prev_node:
prev_node.both = self._xor(id(self.tail), prev_node.both)
else:
self.head = None
# Remove the current tail from the nodes dictionary and update the tail pointer
del self.nodes[id(self.tail)]
self.tail = prev_node
def print_list(self):
"""Prints the entire list from head to tail."""
current = self.head
prev_id = 0
while current:
print(current.data, end=" ")
# Compute the ID of the next node
next_id = self._xor(prev_id, current.both)
# Move the pointers
prev_id = id(current)
current = self.nodes.get(next_id)
print()
if __name__ == '__main__':
list_ = XORLinkedList()
list_.insert_at_head(10)
list_.insert_at_head(20)
list_.insert_at_tail(30)
list_.insert_at_tail(40)
list_.print_list() # Expected: 20 10 30 40
list_.delete_from_head()
list_.print_list() # Expected: 10 30 40
list_.delete_from_tail()
list_.print_list() # Expected: 10 30
using System;
using System.Collections.Generic;
class Node {
public int Data;
public IntPtr Both; // XOR of next and previous node IDs
public int Id; // Unique ID for the node
public Node(int data, int id)
{
Data = data;
Both = IntPtr.Zero;
Id = id;
}
}
class XORLinkedList {
private Node head;
private Node tail;
private Dictionary<int, Node> nodes
= new Dictionary<int, Node>();
private int counter
= 0; // Counter to simulate unique IDs
// Helper function to get the XOR of two IDs
private IntPtr XOR(IntPtr a, IntPtr b)
{
return (IntPtr)((ulong)a ^ (ulong)b);
}
// Get the next unique ID
private int GetNextId() { return ++counter; }
// Insert a node with the provided data at the specified
// position
public void Insert(int data, bool atBeginning = false)
{
int newNodeId = GetNextId();
Node newNode = new Node(data, newNodeId);
nodes[newNodeId] = newNode;
if (head != null && !atBeginning) {
newNode.Both
= XOR((IntPtr)tail.Id, IntPtr.Zero);
tail.Both
= XOR(XOR((IntPtr)tail.Both, IntPtr.Zero),
(IntPtr)newNodeId);
}
else {
newNode.Both = XOR(
IntPtr.Zero, head != null ? (IntPtr)head.Id
: IntPtr.Zero);
if (head != null) {
head.Both = XOR(
(IntPtr)newNodeId,
XOR((IntPtr)head.Both, IntPtr.Zero));
}
else {
tail = newNode;
}
head = newNode;
}
}
// Delete a node from the specified position
public void Delete(bool fromBeginning = true)
{
if (head != null) {
int idToDelete
= fromBeginning ? head.Id : tail.Id;
int nextNodeId = (int)XOR(
IntPtr.Zero,
fromBeginning ? head.Both : tail.Both);
Node nextNode = nodes.ContainsKey(nextNodeId)
? nodes[nextNodeId]
: null;
if (nextNode != null) {
nextNode.Both = XOR(nextNode.Both,
(IntPtr)idToDelete);
}
else {
tail = null;
}
nodes.Remove(idToDelete);
if (fromBeginning) {
head = nextNode;
}
else {
tail = nextNode;
}
}
}
// Print the elements of the list
public void PrintList()
{
Node current = head;
while (current != null) {
Console.Write(current.Data + " ");
int nextId
= (int)XOR(IntPtr.Zero, current.Both);
current = nodes.ContainsKey(nextId)
? nodes[nextId]
: null;
}
Console.WriteLine();
}
}
class Program {
static void Main()
{
XORLinkedList list = new XORLinkedList();
list.Insert(10);
list.Insert(20, true);
list.Insert(30);
list.Insert(40);
// prints 20 10 30 40
list.PrintList();
list.Delete(true);
// prints 10 30 40
list.PrintList();
list.Delete(false);
// prints 10 30
list.PrintList();
}
}
class Node {
constructor(data, id) {
this.data = data;
this.both = 0; // XOR of next and previous node IDs
this.id = id; // Unique ID for the node
}
}
class XORLinkedList {
constructor() {
this.head = this.tail = null;
this.nodes = new Map();
this.counter = 0; // Counter to simulate unique IDs
}
_xor(a, b) {
return a ^ b;
}
getNextId() {
return ++this.counter;
}
insert(data, atBeginning = false) {
const newNodeId = this.getNextId();
const newNode = new Node(data, newNodeId);
this.nodes.set(newNodeId, newNode);
if (this.head && !atBeginning) {
newNode.both = this._xor(this.tail.id, 0);
this.tail.both = this._xor(this._xor(this.tail.both, 0), newNodeId);
} else {
newNode.both = this._xor(0, this.head ? this.head.id : 0);
if (this.head) {
this.head.both = this._xor(newNodeId, this._xor(this.head.both, 0));
} else {
this.tail = newNode;
}
this.head = newNode;
}
}
delete(fromBeginning = true) {
if (this.head) {
const idToDelete = fromBeginning ? this.head.id : this.tail.id;
const nextNodeId = this._xor(0, fromBeginning ? this.head.both : this.tail.both);
const nextNode = this.nodes.get(nextNodeId) || null;
if (nextNode) {
nextNode.both = this._xor(nextNode.both, idToDelete);
} else {
this.tail = null;
}
this.nodes.delete(idToDelete);
if (fromBeginning) {
this.head = nextNode;
} else {
this.tail = nextNode;
}
}
}
printList() {
let current = this.head;
while (current) {
process.stdout.write(current.data + " ");
const nextId = this._xor(0, current.both);
current = this.nodes.get(nextId) || null;
}
process.stdout.write('\n');
}
}
// Example usage
const list = new XORLinkedList();
list.insert(10);
list.insert(20, true);
list.insert(30);
list.insert(40);
list.printList();
list.delete(true);
list.printList();
list.delete(false);
list.printList();
Output
20 10 30 40 10 0 10 10 0 10
Time Complexity: O(n)
Auxiliary Space: O(1)
XOR Linked List – A Memory Efficient Doubly Linked List | Set 1
In this post, we’re going to talk about how XOR linked lists are used to reduce the memory requirements of doubly-linked lists.
We know that each node in a doubly-linked list has two pointer fields which contain the addresses of the previous and next node. On the other hand, each node of the XOR linked list requires only a single pointer field, which doesn’t store the actual memory addresses but stores the bitwise XOR of addresses for its previous and next node.
Following are the Ordinary and XOR (or Memory Efficient) representations of the Doubly Linked List:
In this section, we will discuss both ways in order to demonstrate how XOR representation of doubly linked list differs from ordinary representation of doubly linked list.
- Ordinary Representation
- XOR List Representation
Ordinary Representation of doubly linked list.
Node A:
prev = NULL, next = add(B) // previous is NULL and next is address of BNode B:
prev = add(A), next = add(C) // previous is address of A and next is address of CNode C:
prev = add(B), next = add(D) // previous is address of B and next is address of DNode D:
prev = add(C), next = NULL // previous is address of C and next is NULL
XOR List Representation of doubly linked list.
Lets see the structure of each node of Doubly linked list and XOR linked list:
Below is the representation of a node structure for an XOR linked list:
struct Node {
int data;
// "both": XOR of the previous and next node addresses
Node* both;
};
class Node {
int data;
Node both; // XOR of the previous and next node addresses
}
class Node:
def __init__(self, data):
self.data = data # Data stored in the node
self.prev = None # Reference to the previous node
self.next = None # Reference to the next node
class DoublyLinkedList:
def __init__(self):
self.head = None # Reference to the first node
self.tail = None # Reference to the last node
# Other methods of Doubly Linked List can be implemented here
class Node {
constructor(data) {
this.data = data; // Data stored in the node
this.both = null; // XOR of the previous and next node addresses
}
}
// In JavaScript, there's no native XOR operation on memory addresses like in C/C++
// You can simulate similar behavior using references or pointers to nodes
// However, JavaScript does not provide direct memory manipulation, so XOR operation on addresses is not feasible
// Instead, you can simply store references to the previous and next nodes directly
// For example:
class DoublyLinkedList {
constructor() {
this.head = null; // Reference to the first node
this.tail = null; // Reference to the last node
}
// Other methods of Doubly Linked List can be implemented here
}