This is a C Program to implement XOR list. An XOR linked list is a data structure used in computer programming. It takes advantage of the bitwise XOR operation to decrease storage requirements for doubly linked lists.

Here is source code of the C Program to Implement Xor Linked List. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include <stdio.h>`

`#include <stdlib.h>`

`// Node structure of a memory efficient doubly linked list`

struct node {

int data;

struct node* npx; /* XOR of next and previous node */

};

`/* returns XORed value of the node addresses */`

struct node* XOR(struct node *a, struct node *b) {

return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));

`}`

`/* Insert a node at the begining of the XORed linked list and makes the`

`newly inserted node as head */`

void insert(struct node **head_ref, int data) {

`// Allocate memory for new node`

struct node *new_node = (struct node *) malloc(sizeof(struct node));

new_node->data = data;

`/* Since new node is being inserted at the begining, npx of new node`

`will always be XOR of current head and NULL */`

new_node->npx = XOR(*head_ref, NULL);

`/* If linked list is not empty, then npx of current head node will be XOR`

`of new node and node next to current head */`

if (*head_ref != NULL) {

`// *(head_ref)->npx is XOR of NULL and next. So if we do XOR of`

`// it with NULL, we get next`

struct node* next = XOR((*head_ref)->npx, NULL);

(*head_ref)->npx = XOR(new_node, next);

`}`

`// Change head`

*head_ref = new_node;

`}`

`// prints contents of doubly linked list in forward direction`

void printList(struct node *head) {

struct node *curr = head;

struct node *prev = NULL;

struct node *next;

printf("Following are the nodes of Linked List: \n");

while (curr != NULL) {

`// print current node`

printf("%d ", curr->data);

`// get address of next node: curr->npx is next^prev, so curr->npx^prev`

`// will be next^prev^prev which is next`

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

`// update prev and curr for next iteration`

prev = curr;

curr = next;

`}`

`}`

`// Driver program to test above functions`

int main() {

`/* Create following Doubly Linked List`

`head-->40<-->30<-->20<-->10 */`

struct node *head = NULL;

insert(&head, 10);

insert(&head, 20);

insert(&head, 30);

insert(&head, 40);

`// print the created list`

printList(head);

return (0);

`}`

Output:

$ gcc XORList.c $ ./a.out Following are the nodes of Linked List: 40 30 20 10

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

advertisement

advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

**Next Steps:**

- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Practice Computer Science MCQs
- Buy Data Structure Books
- Apply for Information Technology Internship
- Apply for Data Structure Internship
- Buy Programming Books