Problem with destructor for linked list

[sid78669]

Can someone please tell me why I might be getting a access violation when doing the following for a double linked list:

~DLList()
{
   while(!isEmpty()) //isEmpty is working..
         removeHead();
}

bool isEmpty()
	{
		if(head == NULL && tail == NULL)
			return true;
		else
			return false;
	}

char * removeHead()
	{
		if(!isEmpty())
		{
			ListNode<char *> *temp = head;
			char * tempData = temp->data;
			cout << temp->data;			
				
			if(head == tail)
				head = tail = NULL;
			else {
				head = head->next;
				head->previous = NULL;
			}

			if(temp != NULL && temp->data != NULL){
				delete temp; //--->breaks here
			}

			length--;
			return tempData;
		} else
			exit(1);
	}

[sid78669]

Also, ListNode does not utilise any pointers so its destructor is empty.

[sid78669]

Tried this but din't work either:

~DLList()
	{
		cout << "Destroying List" << endl;
		while(!isEmpty()){
			ListNode<char *> *temp = head;
			head = head->next;
			head->previous = NULL;
			delete temp;
		}
		length = 0;
	}

[sid78669]

OK, so the problem seems to be that the 'temp' variable is already deleted when 'delete temp' occurs after a couple of deletes. But the list still exists in a fairly good condition. Any suggestions on how I may check to see if temp has not been deleted already?

[firstPerson]

Lets examine this for a second :

while(!isEmpty()){
	ListNode<char *> *temp = head;
	head = head->next;
	head->previous = NULL;
	delete temp;
}

Assume that the list contains, A,B,C. Where A-C can be anything.
Now your delete function will do this :

//Iteration # 1

1) while(!isEmpty()) is true go the code block will get executed.
2) ListNode *temp = head; Now Type is any data type. Now temp points to the head which points to A.
3) head = head->next; now head points to B
4) head->previous = NULL; now head->previous points to A right? So you are setting A to null. Remember temp points to A, so temp now is null. This is called amemory leak.
5) delete temp; now you delete a null, which does nothing.

//Iteration # 2
//now the list is {null B C }, where null means it does not exist
1) while(!isEmpty()) this is true so the block of code gets executed
2) ListNode *temp = head; Now temp points to the head which points to B.
3) head = head->next; now head points to C
4) head->previous = NULL; now head->previous points to B right? So you are setting B to null. Remember temp points to B, so temp now is null. This is called a memory leak.
5) delete temp; Now you delete a null, which does nothing.

//Iteration # 3
//now the list is {null null C }, where null means it does not exist
1) while(!isEmpty()) this is true so the block of code gets executed
2) ListNode *temp = head; Now temp points to the head which points to C.
3) head = head->next; now head points to null
4) head->previous = NULL; //now you effectively do , null->previous. Which means that you are now using a null points. This is the reason why you get the access violation exception, since head now points to something else that its has the privilege to.

Now your code is very close. Just fix a few things. If you need more hint
then don't hesitate to ask.

[sid78669]

ok, i made the destructor use the remove head function, it is as this:

~DLList()
{
       while(!isEmpty())
                removeHead();
}

char * removeHead(){
if(!isEmpty())
		{
			ListNode<char *> *temp = head;
			
			char * tempData = temp->data;
				
			if(head == tail){
				head = tail = NULL;
			}
			else {
				head = head->next;
			}

			delete temp;
			if(head->previous != NULL)
				head->previous = NULL;

			length--;
			return tempData;
		} else
			exit(1);
	}

This is still returning the same access violation.

[firstPerson]

This is not java, setting head and tail to NULL will not free the memory. Thus you have a memory leak. Try something like this :

void destroy(){
 Node *pos = _head;
 while(pos != NULL){
   increment(_head); //make head point to next element
   release(pos); //delete the memory pointed by pos.
   pos = _head; 
 }
}

[sid78669]

This is not java, setting head and tail to NULL will not free the memory. Thus you have a memory leak. Try something like this :

void destroy(){
 Node *pos = _head;
 while(pos != NULL){
   increment(_head); //make head point to next element
   release(pos); //delete the memory pointed by pos.
   pos = _head; 
 }
}

The thing is that the error is not generated when there are a few items in the list. But if I have around 45-50 items, the list goes half way and crashes. As for the head=tail thing, that happens only when there is just one item, which at the moment is working. Is there a way to catch the exception here and in case of an error, skip it and move on? I know this is HIGHLY unrecommended, but I am gettin desperate now!!

[firstPerson]

Dude, I practically gave you the answer. Try something like this :

~DLList()
{        //Type is any data type
 	ListNode<Type> *temp = head;
	  while(temp != NULL){
  	  head = head->next;
	  delete temp;
                  temp = head;
	}
	length = 0;
}

[sid78669]

That is what I did. Unfortunately, I am still gettin the access violation so am going to show it to my prof tomorrow.

[thomas_naveen]

I hope your prof has helped you.

If not, could you post the entire code? (with inputs given)

[thomas_naveen]

Take a look at how you are allocating memory in your ListNode.

It might be a good idea to explicitly allocate memory for your pointers there and ensure that the memory is allocated on the heap, rather than assuming that the memory is allocated somewhere.

[sid78669]

OK< I found the problem. I was using a character array in the beginning of the program and due to copying-pasting a piece of code, I had made a mathematical error for the size of array. The problem came to light when the array was being deleted beyond its allocated size! Thanks to all for brainstorming with me.