Jump to content
  • Advertisement
Sign in to follow this  
barakat

Circular Linked List

This topic is 5048 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i am implementing a Double Linked Circular List ...i have a BUG in the "previous" pointer...
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;
};

[edit: added [source] tags -SiCrane]

Share this post


Link to post
Share on other sites
Advertisement
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:

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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!