data structure , doubly linked list . probelm

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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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.
Try below,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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...
Last edited on
welcome richardforc , thanks for trying to help :)

I checked the new code but not working :(

ok see all code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
#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 ;
}


Try this one. I think it will work (untested though):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
Last edited on
Topic archived. No new replies allowed.