Xor Linked List in C

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.

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

« Prev - C Program to Implement Stack using Two Queues

» Next - C Program to Implement Hash Tables Chaining with Linked Lists

Related Posts:

Practice Programming MCQs
Check Data Structure Books
Practice Computer Science MCQs
Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: