data structure , doubly linked list . probelm

[zizo1989]

hi every one, sorry if I write this topic in wrong section :'(

I have a problem with this code I dont know why is not compiling or show result !!

this is the questoin:
----------------------------------
Write a function that deletes all nodes which has an index
that is a multiple of three i.e. after every two nodes, delete the
third one.
void DLL::specialDelete();

Original List {2,5,7,4,1,3,8}
Function Call specialDelete()
Resulted List {2,5,4,1,8}


and this my function:

void DLL::specialDelete()
{
	Node *cur = head;
	Node *prev = head;
	int count = 1;
	while ( cur != NULL ) 
	{
		count++;
		if ( count % 3 == 0 )
		{
			prev->next = cur->next;
			//delete cur;
			cur->next->prev = cur;
			
		}
		    
			prev = cur;
			cur = cur->next;
		
	}
}

I have the all code if you want it let me know
I hope find any suggestions.

[richardforc]

Try below,

void DLL::specialDelete()
{
	Node *cur = head;
	Node *prev = head;
	int count = 1;
	while ( cur != NULL ) 
	{
		count++;
		if ( count % 3 == 0 )
		{
			prev->next = cur->next;
			//delete cur;
			cur->next->prev = prev; // not cur, cur need to be removed.
                       // e.g, p1<-->p2<-->p3<-->p4, 
                       //at deletion of p3.
		       // p1<-->p2<-->p4, p4 should point to p2, not p3.
		}
		    
			prev = cur;
			cur = cur->next;
		
	}
}

Also, need to check adding of nodes. Make sure you created doubly linked list, not circular linked list, i.e in last node next should not be first node.

Check with the above changes... If not works post code...

[zizo1989]

welcome richardforc , thanks for trying to help :)

I checked the new code but not working :(

ok see all code

#include <iostream>
using namespace std ;

//################################## Node Class ###################################
class Node
{
	public :
			int data ;
			Node * next ;
			Node * prev ;

			Node()
			{
				next = NULL ;
				prev = NULL ;
				data = -1 ;
			}
};
//################################End of Node Class ################################

//################################### DLL Class ####################################
class DLL
{
	public :
			Node * head ;
			DLL() ;
			~DLL() ;
			bool isEmpty() ;
			void build(int arr[],int size) ;
			void print() ;
			bool cmp(int arr[],int size) ;
			void specialDelete() ;

};

DLL::DLL()
{
	head = NULL ;
}

DLL::~DLL()
{
	while(head != NULL)
	{
		Node * p = head ;
		head = head->next ;
		delete p ;
	}
}

bool DLL::isEmpty()
{
	return head == NULL ;
}

void DLL::build(int arr[],int size)
{
	head = new Node() ;
	head->data = arr[0] ;
	Node * current = head ;
	for(int i=1;i<size;i++)
	{
		current->next = new Node() ;
		current->next->data = arr[i] ;
		current->next->prev = current ;
		current = current->next ;
	}
}

void DLL::print()
{
	if(head == NULL)
	{
		cout << "Empty List" << endl ;
	}
	else
	{
		cout << "{" ;
		Node * current = head ;
		while(current->next !=NULL)
		{
			cout << current->data << "," ;
			current = current->next ;
		}
		cout << current->data << "}" << endl ;
	}
}


bool DLL::cmp(int arr[],int size)
{
	if(head == NULL && size == 0)
	{
		return true ;
	}
	Node * c = head ;
	for(int i=0;i<size;i++)
	{
		if(c == NULL)
		{
			return false ;
		}
		if(c->data != arr[i])
		{
			return false ;
		}
		c = c->next ;
	}
	if(c != NULL)
	{
		return false ;
	}
	
	return true ;
}

void DLL::specialDelete()
{
	Node *cur = head;
	Node *prev = head;
	int count = 1;
	while ( cur != NULL ) 
	{
		count++;
		if ( count % 3 == 0 )
		{
			prev->next = cur->next;
			//delete cur;
			cur->next->prev = prev; // not cur, cur need to be removed.
                       // e.g, p1<-->p2<-->p3<-->p4, 
                       //at deletion of p3.
		       // p1<-->p2<-->p4, p4 should point to p2, not p3.
		}
		    
			prev = cur;
			cur = cur->next;
		
	}
}

//###################################End of DLL Class ###############################

int main()
{
	{
		cout << "General Case (not a multiple of 3):" << endl ;
		DLL x ;
		int arr[] = {1,2,3,4,5,6,7,8,9,10} ;
		x.build(arr,10) ;
		cout << "   " ;
		x.specialDelete() ;
		x.print() ;
		cout << "R :{1,2,4,5,7,8,10}" << endl ;
		int arr2[] = {1,2,4,5,7,8,10} ;
		if(x.cmp(arr2,7))
		{
			cout << "-------PASS-------" << endl ;
		}
		else
		{
			cout << "#######ERROR#######" << endl ;
		}
		
	}


	{
		cout << "General Case (multiple of 3):" << endl ;
		DLL x ;
		int arr[] = {1,2,3,4,5,6,7,8,9} ;
		x.build(arr,9) ;
		cout << "   " ;
		x.specialDelete() ;
		x.print() ;
		cout << "R :{1,2,4,5,7,8}" << endl ;
		int arr2[] = {1,2,4,5,7,8} ;
		if(x.cmp(arr2,6))
		{
			cout << "-------PASS-------" << endl ;
		}
		else
		{
			cout << "#######ERROR#######" << endl ;
		}
		
	}

	{
		cout << "Empty List:" << endl ;
		DLL x ;
		int arr[] = {1,2,3,4,5,6,7,8,9,10} ;
		//x.build(arr,10) ;
		//cout << "   " ;
		x.specialDelete() ;
		x.print() ;
		//cout << "R :{1,2,4,5,7,8,10}" << endl ;
		int arr2[] = {1,2,4,5,7,8,10} ;
		if(x.head == NULL)
		{
			cout << "-------PASS-------" << endl ;
		}
		else
		{
			cout << "#######ERROR#######" << endl ;
		}
		
	}

	{
		cout << "One Node:" << endl ;
		DLL x ;
		int arr[] = {1} ;
		x.build(arr,1) ;
		cout << "   " ;
		x.specialDelete() ;
		x.print() ;
		cout << "R :{1}" << endl ;
		int arr2[] = {1} ;
		if(x.cmp(arr2,1))
		{
			cout << "-------PASS-------" << endl ;
		}
		else
		{
			cout << "#######ERROR#######" << endl ;
		}
		
	}

	{
		cout << "Two Nodes:" << endl ;
		DLL x ;
		int arr[] = {1,2} ;
		x.build(arr,2) ;
		cout << "   " ;
		x.specialDelete() ;
		x.print() ;
		cout << "R :{1,2}" << endl ;
		int arr2[] = {1,2} ;
		if(x.cmp(arr2,2))
		{
			cout << "-------PASS-------" << endl ;
		}
		else
		{
			cout << "#######ERROR#######" << endl ;
		}
		
	}
	system("pause");
	return 0 ;
}

[D80DSL3A]

Try this one. I think it will work (untested though):

void DLL::specialDelete()
{
	Node *cur = head;
	int count = 0;// start at 0
	while ( cur != NULL ) 
	{
		count++;// 1-head, 2-(head+1), 3-(head+2)
		if ( count % 3 == 0 )// delete curr
		{
			Node* temp = cur;
			// deletion of cur = p3.
			cur->prev->next = cur->next;// p2-->p4
                        if( cur->next != NULL )
              		      cur->next->prev = cur->prev;// p2<--p4
			cur = cur->next;// cur=p4
			delete temp;
		}
		else
			cur = cur->next;// also done in if()	
	}
}

EDIT: Added line 13 to test cur-> for NULL