class node{
public:
node(char ch):data(ch),next(0),previous(0){ }
char data;
node * next;
node * previous;
};
class circularList{
public:
circularList():last(0){ }
void insert(const char ch)
{
node * newNode = new node(ch);
assert(newNode);
if(isEmpty()){
//sth wrong here
last = newNode;
last->next = newNode;
last->previous = newNode;
}
else{
//or may be here :D
last->next = newNode;
newNode->next = last->next;
newNode->previous = last;
last = newNode;
}
}
bool isEmpty(){return last==0;}
private:
node * last;
};
Circular Linked List
Author
i am implementing a Double Linked Circular List ...i have a BUG in the "previous" pointer...
[edit: added [source] tags -SiCrane]
When you add a new node in when you already have existing nodes, you try to insert it after last.
So after the insertion you want last->next to be equal to newNode, newNode->next to be equal to the old last->next, newNode->prev to be equal to last and the old last->next's prev to be equal to newNode.
So the order to do this, one order of assignments to get it to work without temporaries would be:
In your previous code, you assign newNode->next to be equal to last->next after assigning newNode to last->next, which will cause newNode->next to always be equal to newNode, which will break the circularity of your linked list. Also, you never assign last->next->prev, which means that walking backwards through your list will skip nodes.
So after the insertion you want last->next to be equal to newNode, newNode->next to be equal to the old last->next, newNode->prev to be equal to last and the old last->next's prev to be equal to newNode.
So the order to do this, one order of assignments to get it to work without temporaries would be:
last->next->prev = newNode; newNode->prev = last; newNode->next = last->next; last->next = newNode; last = newNode;In your previous code, you assign newNode->next to be equal to last->next after assigning newNode to last->next, which will cause newNode->next to always be equal to newNode, which will break the circularity of your linked list. Also, you never assign last->next->prev, which means that walking backwards through your list will skip nodes.
Good to see someone implementing a circular-doubly-linked-list (or ring-list as I like to call it). They have the advantage over double-ended-lists that you need only store one pointer to the list and you can still start from either 'end'.
Also, if you try and implement merge-sort for this data structure you'll come across the interesting phenomenon, that the code to split one ring list into two, is identical to the code that joins two ring-lists back into one.
It sounds like you've got your code sorted out now (excuse the pun), but if you have any other troubles I could post my own templated ring-list code.
Happy coding!
Also, if you try and implement merge-sort for this data structure you'll come across the interesting phenomenon, that the code to split one ring list into two, is identical to the code that joins two ring-lists back into one.
It sounds like you've got your code sorted out now (excuse the pun), but if you have any other troubles I could post my own templated ring-list code.
Happy coding!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
