XOR linked lists are a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction (XOR) operation to decrease storage requirements for doubly-linked lists.
http://en.wikipedia.org/wiki/XOR_linked_list
Compile as console exe
declare import, system(...);
sub main()
{
print("XOR linked list\n");
list_xor();
cls();
print("Addition linked list\n");
list_add();
cls();
print("Subtraction linked list\n");
list_sub();
cls();
}
struct LISTNODE
{
DWORD Link; // pointer to next/prev
string *name; // any data
}
sub list_xor()
{
LISTNODE A; LISTNODE *first = A;
LISTNODE B;
LISTNODE C;
LISTNODE D; LISTNODE *last = D;
// initialize the linked list
A.Link = NULL xor &B; // prev xor next
B.Link = &A xor &C;
C.Link = &B xor &D;
D.Link = &C xor NULL;
A.name = "A";
B.name = "B";
C.name = "C";
D.name = "D";
LISTNODE *node;
LISTNODE *prev;
LISTNODE *next;
print("iterate forward");
prev = NULL;
node = first;
while (node)
{
print("node name: ", node->*name);
next = prev xor node->Link;
prev = node;
node = next;
}
print("\niterate backward");
node = last;
next = NULL;
while (node)
{
print("node name: ", node->*name);
prev = next xor node->Link;
next = node;
node = prev;
}
print();
system("pause");
}
sub list_add()
{
LISTNODE A; LISTNODE *first = A;
LISTNODE B;
LISTNODE C;
LISTNODE D; LISTNODE *last = D;
// initialize the linked list
A.Link = NULL + &B; // prev + next
B.Link = &A + &C;
C.Link = &B + &D;
D.Link = &C + NULL;
A.name = "A";
B.name = "B";
C.name = "C";
D.name = "D";
LISTNODE *node;
LISTNODE *prev;
LISTNODE *next;
print("iterate forward");
prev = NULL;
node = first;
while (node)
{
print("node name: ", node->*name);
next = node->Link - prev;
prev = node;
node = next;
}
print("\niterate backward");
node = last;
next = NULL;
while (node)
{
print("node name: ", node->*name);
prev = node->Link - next;
next = node;
node = prev;
}
print();
system("pause");
}
sub list_sub()
{
LISTNODE A; LISTNODE *first = A;
LISTNODE B;
LISTNODE C;
LISTNODE D; LISTNODE *last = D;
// initialize the linked list
A.Link = &B - NULL; // next - prev
B.Link = &C - &A;
C.Link = &D - &B;
D.Link = NULL - &C;
A.name = "A";
B.name = "B";
C.name = "C";
D.name = "D";
LISTNODE *node;
LISTNODE *prev;
LISTNODE *next;
print("iterate forward");
prev = NULL;
node = first;
while (node)
{
print("node name: ", node->*name);
next = node->Link + prev;
prev = node;
node = next;
}
print("\niterate backward");
node = last;
next = NULL;
while (node)
{
print("node name: ", node->*name);
prev = -(node->Link - next);
next = node;
node = prev;
}
print();
system("pause");
}
Cool!
thanks for sharing.
Haim