1 Replies - 38180 Views - Last Post: 18 November 2006 - 12:06 AM Rate Topic: -----

#1 :-P  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 17-November 06

circular doubly linked list

Posted 17 November 2006 - 10:07 PM

[font=Arial][font=Arial][font=Arial] :huh:
hey :)
i have this program for a singly linked list which is basically just using functions on it, and i need to convert it to a circular doubly linked list...it seems like it should be easy, but when i do what i think shud be done, it messes up on me, and either gives me error messages or basically tells me that the pointers m using dont exist...i think... lol
ive spent a lot of time on it already and i just dont understand why the derned thing won't work...
so, here's the implementation file of the unchanged and fully functional singly linked list:
(the node for the circular double linked list wud hold:
and int value;
a next pointer;
a prev pointer;
)


//************************************[font=Arial][font=Arial][font=Arial]
//Implementation File (list.cpp)
//*****************************************

#include <iostream>
#include <fstream>
#include "list.h"
using namespace std;

List::List()
{
	head = '\0';
}

void List::showReverse(Node *pointer, fstream &out) const
{
	if(pointer!='\0')
	{
		showReverse(pointer->next,out);
		out << pointer->data << endl;
	}
}

void List::insertNode(int num)
{
	Node *newNode;
	Node *nodePtr;
	Node *previous = '\0';
	newNode = new Node;
	newNode->data = num;

	if(!head)
	{
		head = newNode;
		newNode->next = '\0';
	}
	else
	{
		nodePtr = head;
		previous = '\0';
		while(nodePtr!='\0' && (nodePtr->data < num))
		{
			previous = nodePtr;
			nodePtr = nodePtr->next;
		}
		if(previous == '\0')
		{
			head = newNode;
			newNode->next = nodePtr;
		}
		else
		{
			previous->next = newNode;
			newNode->next = nodePtr;
		}
	}
}

void List::printForward(fstream &out)const
{
	Node *p;		//to move through the list
	p = head;		//position p pointer at head of list
	while(p)
	{
		out << p->data << endl;			//display value
		p = p->next;					//move to the next node
	}
	out << endl;
}

void List::printBackward(fstream &out)const
{
	showReverse(head,out);
	out << endl;
}

void List::deleteNode(int num)
{
	Node *nodePtr;
	Node *prevNode;

	if(head=='\0')
		return;
	if(head->data == num)
	{
		nodePtr = head->next;
		delete head;
		head = nodePtr;
	}
	else
	{
		nodePtr = head;
		while(nodePtr!='\0' && (nodePtr->data!=num))
		{
			prevNode = nodePtr;
			nodePtr = nodePtr->next;
		}
		if(nodePtr)
		{
			prevNode->next = nodePtr->next;
			delete nodePtr;
		}
	}
}

void List::merge(List list1, List list2)
{
	Node *ptr1;
	Node *ptr2;
	ptr1 = list1.head;
	while(ptr1!='\0')
	{
		insertNode(ptr1->data);
		ptr1 = ptr1->next;
	}
	ptr2 = list2.head;
	while(ptr2!='\0')
	{
		insertNode(ptr2->data);
		ptr2 = ptr2->next;
	}
}



again, im trying to make these functions work on a circular doubly linked list...print backward would use the prev pointer and not a recursive function...i think... ;)
thanks!!

Is This A Good Question/Topic? 0
  • +

Replies To: circular doubly linked list

#2 gregoryH  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 60
  • View blog
  • Posts: 656
  • Joined: 04-October 06

Re: circular doubly linked list

Posted 18 November 2006 - 12:06 AM

View Post:-P, on 17 Nov, 2006 - 10:07 PM, said:

[font=Arial][font=Arial][font=Arial] :huh:
hey :)
i have this program for a singly linked list which is basically just using functions on it, and i need to convert it to a circular doubly linked list...it seems like it should be easy, but when i do what i think shud be done, it messes up on me, and either gives me error messages or basically tells me that the pointers m using dont exist...i think... lol
ive spent a lot of time on it already and i just dont understand why the derned thing won't work...
so, here's the implementation file of the unchanged and fully functional singly linked list:
(the node for the circular double linked list wud hold:
and int value;
a next pointer;
a prev pointer;
)


	head = '\0';
	if(pointer!='\0')
	Node *previous = '\0';
		newNode->next = '\0';
		previous = '\0';
		while(nodePtr!='\0'
		if(previous == '\0')
	if(head=='\0')
		while(nodePtr!='\0' && (nodePtr->data!=num))
	while(ptr1!='\0')
	while(ptr2!='\0')



again, im trying to make these functions work on a circular doubly linked list...print backward would use the prev pointer and not a recursive function...i think... ;)
thanks!!

Hi,

Since you didn't post any of your error messages, we have no way of knowing what you saw, or if its related to compile time or run time.

I have singled out some lines that look wrong. previous is of type Node, and you are assigning a type of char to it. While C/C++ will try to automatically make a conversion, a better way to deal with that is to use the NULL to ensure a known value is inserted to the variables. IE Node * previous = NULL;.

Using the picture I have supplied, you need to iterate in previous or next direction from head, ie
currentnode=head;
do{
  printnode( currentnode );
  currentnode = currentnode->next;
}while ( currentnode != head );

Attached image(s)

  • Attached Image

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1