Unsorted Link List Delete Function Error

[bird1234]

Whenever i use deleteitem() function my compiler point me to the show() function

  Header File "Node"
  struct Node
{
	int data;
	Node* next;
};

 Header File "UnsortedList"
 #ifndef _UNSORTEDLIST_H
#define _UNSORTEDLIST_H

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


class unsortedList
{
public:
	unsortedList();
	~unsortedList();
	void InsertItem(int item);
	void DeleteItem(int item);
	int ShowLength();
	void Show();
	void MakeEmpty();
	bool isFull();
private:
	int length;
	Node* start;
};
#endif 

 cpp File"UnsortedList"
 #include"UnsortedList.h"

unsortedList::unsortedList()
{
	length = 0;
	start = NULL;
}

int unsortedList::ShowLength()
{
	return length;
}

void unsortedList::InsertItem(int item)
{
	Node* temp = new Node;

	temp->data = item;
	temp->next = start;
	start = temp;

	length++;

}

bool unsortedList::isFull()
{
	Node* location;
	try
	{
		location = new Node;
		delete location;
		return false;
	}
	catch (bad_alloc expection)
	{
		return true;
	}
}

unsortedList::~unsortedList()
{
	MakeEmpty();
}

void unsortedList::MakeEmpty()
{
	Node* empty;
	while (start != NULL)
	{
		empty = start;
		start = start->next;
		delete empty;
	}
	length = 0;
}

void unsortedList::Show()
{
	Node* temp = start;
	while (temp != NULL)
	{
		cout << temp->data << " " << endl;
		temp = temp->next;
	}
}

void unsortedList::DeleteItem(int item)
{
	if (start!= NULL)
	{
		Node* Delete = start;
		if (item == start->data)
		{
			start = start->next;
			delete Delete;
			length--;
		}
		else
		{
			while ((Delete->next != NULL) && (!(item==Delete->next->data)))
			{
				Delete = Delete->next;
			}
			Node* target = Delete->next;
			if (target != NULL)
			{
				Delete->next = target->next;
				delete Delete;
				length--;
			}
		}
	}
}

 cpp "Source"

 #include"UnsortedList.h"

int main()
{
	unsortedList usl;

	usl.InsertItem(5);
	usl.InsertItem(6);
	usl.InsertItem(7);
	usl.InsertItem(8);
	usl.InsertItem(9);


	usl.DeleteItem(8);
	cout << "Length : " << usl.ShowLength() << endl;
	usl.Show();
	system("pause");
} 

Error Pic


http://oi63.tinypic.com/v3q7n7.jpg

[cire]

It is possible for Delete to be equal to start when line 90 of Unsorted.cpp is reached, and thereafter start will be an invalid pointer.

[dhayden]

The immediate problem is line 90 which should be delete target;

If you think about it, at this point in the code you are using variable Delete as the pointer to the previous node in the list. target is the node to delete. If you'd created a separate variable like prev, the code would probably be clearer and you might have avoided the mistake. The point here is that clear variable names are important:

			Node *prev = start;
			while ((prev->next != NULL) && (!(item==prev->next->data)))
			{
				prev = prev->next;
			}
			Delete = prev->next;
			if (Delete != NULL)
			{
				prev->next = Delete->next;
				delete Delete;
				length--;
			}

Personally, I think it's clearer to use a "current" and "previous" pointer, and do the work inside the loop:

Node *cur;
for (Node *prev = start; cur = prev->next; prev = cur) {
	if (cur->data == item) {
		prev->next = cur->next;
		delete cur;
		length--;
		break;
	}
}

Also, it's never a good idea to put a using namespace statement in a header file because that bleeds into every other header file that might be included after the the current one. So move line 7 of UnsortedList.h to line 3 of Unsortedlist.cpp.

But the best way to delete from a linked list is to use a variable that points to start or the next pointer. All of the special cases disappear and the entire delete function becomes just a few lines:

void
unsortedList::DeleteItem(int item)
{
    Node **pStartOrNext, *cur;
    for (pStartOrNext = &start;
	 (cur = *pStartOrNext);
	 pStartOrNext = &cur->next) {

	if (cur->data == item) {
	    *pStartOrNext = cur->next;
	    delete cur;
	    length--;
	    break;
	}
    }
}

[bird1234]

Thnx