Thursday, September 27, 2007

Singly linked list as Doubly

With the linked list the major concern is the space consumed by the pointer in the structure.
For singly linked list, there is one extra pointer in each node to point to the next node.
Similarly in doubly linked list, there are two extra pointers in each node, one point to previous node and other point to next node.
Now depending upon the machine word size, if it is 32 bit, the pointer consume 4 bytes and in 64 bit machine it consumes 64 bits. Which is quite a bit.
I have written a code in C++, which just take the space of a singly linked list but it can be used to traverse both ways like doubly linked list.

#include
using std::cout;
using std::endl;


template
class NODE {
public:
NODE() {
next = NULL;
}
NODE(const TYPE data) : data(data), next(NULL) { }
TYPE getData() {
return data;
}
NODE *getNext() {
return next;
}
void setNext(long next) {
this->next = reinterpret_cast(next);
}
private:
TYPE data;
NODE *next;
};

template
class LIST {
public:
LIST() {
XORdata = head = tail = NULL;
}
void add(TYPE data);
void traverseForward();
void traverseBackward();
private:
NODE *head;
NODE *tail;
NODE *XORdata;
};

template
void LIST::traverseBackward() {
NODE *tempTail = tail;
NODE *tempTail1 = tail;
NODE *tempXOR = XORdata;
while(tempTail) {
cout << "Data : " <<>getData() << p1 =" reinterpret_cast<"> (tempTail->getNext());
long p2 = reinterpret_cast<> (tempXOR);
tempTail = reinterpret_cast *>(p1^p2);
tempXOR = tempTail1;
tempTail1 = tempTail;
}
}

template
void LIST::traverseForward() {
NODE *tempHead = head;
NODE *tempHead1 = head;
NODE *tempXOR = NULL;
while(tempHead) {
cout << "Data : " <<>getData() <<>getNext()) break;
long p1 = reinterpret_cast<> (tempHead->getNext());
long p2 = reinterpret_cast<> (tempXOR);
tempHead = reinterpret_cast *>(p1^p2);
tempXOR = tempHead1;
tempHead1 = tempHead;
}
}

template
void LIST::add(TYPE data) {
if(NULL == head) {
tail = head = new NODE(data);
} else {
NODE *temp = new NODE(data);
long p1 = reinterpret_cast(XORdata);
long p2 = reinterpret_cast(temp);
tail->setNext(p1^p2);
XORdata = tail;
tail = temp;
}
}

int main(int argc, char **argv, char **arge) try {
LIST list;
for(int i = 10; i < 16; ++i )
list.add ( i);
list.traverseForward();
cout << "Now moving backward !!!" << endl;
list.traverseBackward();
return 0;
} catch(...) {
cout << "Uncaught exception!" << endl;
}

3 comments:

Siddhartha Singh said...

Oops because of html tag problems, it is removing template's <> syntax.
Please put yourself the tags and compile the code. Where ever template is written just apply \< \>

ask said...

Hey Sid
Nice page... There are a few observations..
In the linked list code, shouldn't Node be a struct encapsulated in List? That way only list class knows about and manipulates the struct.
Also any bit twiddling should be done on unsigned types. Also there should be an assert...
assert (sizeof(Node*) == sizeof(unsigned long));
A lot of asserts will help a lot...
These days I am thinking a lot about class invariants. So there will be a class method that checks the invariant. This will be called at the start of every method. Ideally, this should be done from within CppUnit before every unit test executes...
I will write my version and submit here...
Thanks a ton for this blog.. great medium to learn from each other.
-- cheerio atul

Siddhartha Singh said...

Yes I agree with your thoughts. Please provide your thoughts as the comment here.
This will help our learning

Cheers,
Siddhartha