March 29, 2024, 02:02:11 AM

News:

Own IWBasic 2.x ? -----> Get your free upgrade to 3.x now.........


XOR linked list

Started by sapero, October 01, 2008, 10:01:27 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

sapero

October 01, 2008, 10:01:27 AM Last Edit: October 01, 2008, 10:07:36 AM by sapero
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");
}

Haim

Cool!
thanks for sharing.

Haim