C Program to Implement Xor Linked List

«
»
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.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Node structure of a memory efficient doubly linked list
  5. struct node {
  6.     int data;
  7.     struct node* npx; /* XOR of next and previous node */
  8. };
  9.  
  10. /* returns XORed value of the node addresses */
  11. struct node* XOR(struct node *a, struct node *b) {
  12.     return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
  13. }
  14.  
  15. /* Insert a node at the begining of the XORed linked list and makes the
  16.  newly inserted node as head */
  17. void insert(struct node **head_ref, int data) {
  18.     // Allocate memory for new node
  19.     struct node *new_node = (struct node *) malloc(sizeof(struct node));
  20.     new_node->data = data;
  21.  
  22.     /* Since new node is being inserted at the begining, npx of new node
  23.      will always be XOR of current head and NULL */
  24.     new_node->npx = XOR(*head_ref, NULL);
  25.  
  26.     /* If linked list is not empty, then npx of current head node will be XOR
  27.      of new node and node next to current head */
  28.     if (*head_ref != NULL) {
  29.         // *(head_ref)->npx is XOR of NULL and next. So if we do XOR of
  30.         // it with NULL, we get next
  31.         struct node* next = XOR((*head_ref)->npx, NULL);
  32.         (*head_ref)->npx = XOR(new_node, next);
  33.     }
  34.  
  35.     // Change head
  36.     *head_ref = new_node;
  37. }
  38.  
  39. // prints contents of doubly linked list in forward direction
  40. void printList(struct node *head) {
  41.     struct node *curr = head;
  42.     struct node *prev = NULL;
  43.     struct node *next;
  44.  
  45.     printf("Following are the nodes of Linked List: \n");
  46.  
  47.     while (curr != NULL) {
  48.         // print current node
  49.         printf("%d ", curr->data);
  50.  
  51.         // get address of next node: curr->npx is next^prev, so curr->npx^prev
  52.         // will be next^prev^prev which is next
  53.         next = XOR(prev, curr->npx);
  54.  
  55.         // update prev and curr for next iteration
  56.         prev = curr;
  57.         curr = next;
  58.     }
  59. }
  60.  
  61. // Driver program to test above functions
  62. int main() {
  63.     /* Create following Doubly Linked List
  64.      head-->40<-->30<-->20<-->10   */
  65.     struct node *head = NULL;
  66.     insert(&head, 10);
  67.     insert(&head, 20);
  68.     insert(&head, 30);
  69.     insert(&head, 40);
  70.  
  71.     // print the created list
  72.     printList(head);
  73.  
  74.     return (0);
  75. }

Output:

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

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.