Skip to content

Instantly share code, notes, and snippets.

@ldd
Created August 5, 2019 03:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ldd/eacf562a8b871aa2891a7303a340dcd6 to your computer and use it in GitHub Desktop.
Save ldd/eacf562a8b871aa2891a7303a340dcd6 to your computer and use it in GitHub Desktop.
double linked list with XOR
#include<stdlib.h>
#include<stdio.h>
struct Node {
int data;
struct Node *both;
};
// https://stackoverflow.com/a/26569748
struct Node * xor(struct Node *m, struct Node *n){
return (struct Node *)((uintptr_t)m ^ (uintptr_t)n);
}
struct Node *head = NULL;
struct Node *previous = NULL;
struct Node *current = NULL;
void add(int data) {
//create a link
struct Node *link = (struct Node*) malloc(sizeof(struct Node));
link->data = data;
if(head == NULL){
link->both = NULL;
head = link;
current = link;
}
else{
link->both = xor(current,NULL);
current->both = xor(previous,link);
previous = current;
current = link;
}
}
struct Node * get(int wantedIndex){
struct Node *node = head;
struct Node *prev = NULL;
struct Node *temp = NULL;
int i = 0;
while(node != NULL){
if(wantedIndex == i){
return node;
}
i++;
temp = node;
node = xor(prev,node->both);
prev = temp;
}
return NULL;
}
void printLinkedList(){
struct Node *node = head;
struct Node *prev = NULL;
struct Node *temp = NULL;
while(node != NULL){
printf("%d\t",node->data);
temp = node;
node = xor(prev,node->both);
prev = temp;
}
}
int main()
{
add(5);
add(7);
add(8);
add(9);
add(11);
printLinkedList();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment