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
}
private:
TYPE data;
NODE *next;
};
template
class LIST {
public:
LIST() {
XORdata = head = tail = NULL;
}
void add(TYPE data);
void traverseForward();
void traverseBackward();
private:
NODE
NODE
NODE
};
template
void LIST
NODE
NODE
NODE
while(tempTail) {
cout << "Data : " <<>getData() << p1 =" reinterpret_cast<"> (tempTail->getNext());
long p2 = reinterpret_cast<> (tempXOR);
tempTail = reinterpret_cast
tempXOR = tempTail1;
tempTail1 = tempTail;
}
}
template
void LIST
NODE
NODE
NODE
while(tempHead) {
cout << "Data : " <<>getData() <<>getNext()) break;
long p1 = reinterpret_cast<> (tempHead->getNext());
long p2 = reinterpret_cast<> (tempXOR);
tempHead = reinterpret_cast
tempXOR = tempHead1;
tempHead1 = tempHead;
}
}
template
void LIST
if(NULL == head) {
tail = head = new NODE
} else {
NODE
long p1 = reinterpret_cast
long p2 = reinterpret_cast
tail->setNext(p1^p2);
XORdata = tail;
tail = temp;
}
}
int main(int argc, char **argv, char **arge) try {
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:
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 \< \>
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
Yes I agree with your thoughts. Please provide your thoughts as the comment here.
This will help our learning
Cheers,
Siddhartha
Post a Comment