Problem With Inserting into Linked List

Hi I am merely trying to insert several nodes into a predefined linked list and the second call to the insert function always messes up for some odd reason. I try to find the error by debugging but Microsoft Visual C++ 6.0 pops up aan error when trying to access the second call to the function. Here is the code:

Code:

#include <iostream>

using namespace std;

struct entry
{
int value;
entry* next;
};

void printList(const entry*);
entry* insert(int n, entry* h);
entry* deleteNode(int n, entry* h);

int main()
{
entry n1, n2, n3, n4, n5, n6, n7, n8, n9, n10;

	n1.value = 2;
	n2.value = 6;
	n3.value = 9;
	n4.value = 13;
	n5.value = 22;
	n6.value = 25;
	n7.value = 30;
	n8.value = 35;
	n9.value = 40;
	n10.value = 50;
	
	n1.next = &n2;
	n2.next = &n3;
	n3.next = &n4;
	n4.next = &n5;
	n5.next = &n6;
	n6.next = &n7;
	n7.next = &n8;
	n8.next = &n9;
	n9.next = &n10;
	n10.next = 0;

	entry* head = &n1;
	
	head = deleteNode(25, head);
	head = deleteNode(50, head);
	head = deleteNode(2, head);

	head = insert(17, head);
	head = insert(75, head);//problem occurs when trying to execute this line
	//head = insert(1, head);

	printList(head);
	return 0;
}//main

/***************************************/

void printList(const entry* pointer)
{
	while(pointer != 0)
	{
		cout << pointer << " " << pointer->value << " " << pointer->next << endl;
		pointer = pointer->next;
	}//while

}//printList

/***************************************/

entry* insert(int n, entry* h)
{
	if(h->value < n)
	{
		entry* prev = h;
		entry* temp = h;

		while(temp->value < n)
		{
			prev = temp;
			temp = temp->next;
			
		}//while
		temp = new entry;
		temp->value = n;
		temp->next = prev->next;
		prev->next = temp;
		return h;
	}//if
	else// if h->value >= n
	{
		entry* temp = h;

		temp = new entry;
		temp->value = n;
		temp->next = h;
		h = temp;
		return h;
	}//else
	
}//insert

/***************************************/

entry* deleteNode(int n, entry* h)
{
	if(h->value == n)
	{
		h = h->next;
		return h;
	}//if
	else
	{
		entry* prev = h;
		entry* temp = h;

		while(temp->value != n)
		{
			prev = temp;
			temp = temp->next;
		}//while

		prev->next = temp->next;
		return h;
	}//else

}//deleteNode

Thanks in advance for any help!

you're messing up static and dynamic allocations for your nodes - this will result in the memory leaks...

You should be consistent about what you do:
if insert is allocation memory - it should do it always, deleteNode should free it and you should use only these 2 functions to modify the list

If your insert just inserts the node in the list, and the memory is allocated somethere alse - and DeleteNode - does not free memory, but just resets pointers to exclude the node from the list - you should be consistent in this behavior as well...

Do not mix them

If you're just trying to insert a node into a sorted list, then you might consider this as well: sorted insertion is just a tiny variation on normal insertion. Where you would normally evaluate two passed pointers you will instead evaluate where a loop breaks. As the list is walked through the loop is going to break because of one of three reasons. Either
the head node is missing or out of order with the new node,
you have to insert the new node after some previous node but before another,
or you're inserting at the tail of a list.

It's easy to avoid leaking memory knowing that. Just look at the previous node and it's next pointer.

Code:

insert( entry *head, entry *that )
{
  if ( that )
  {
    entry *prev = NULL, *iter = head;

    while ( iter )
    {
      if ( iter->data < that->data )
      {
        prev = iter;
        iter = iter->next;
      }
      else
        break;
    }

    if ( prev && prev->next )
    {
      that->next = prev->next;
      prev->next = that;
    }
    else if ( prev )
    {
      prev->next = that;
      that->next = NULL;
    }
    else
    {
      if ( head )
        that->next = head;
      else
        head = that;
    }
  }
}

note that

Code:

if ( prev && prev->next )
    {
      that->next = prev->next;
      prev->next = that;
    }
    else if ( prev )
    {
      prev->next = that;
      that->next = NULL;
    }

if prev->next is null both ifs do the same...
so this part can be (removing unnecesary brancing)

Code:

if ( prev)
{
      that->next = prev->next;
      prev->next = that;
}

Code:

<---------find---------------------->
	while( temp->value < n )
		{
			prev = temp;
			temp = temp->next;

		}//while
//---------------------------------------------
<-----------replace with-------------------->

	while(temp!=NULL && temp->value < n )
		{
			prev = temp;
			temp = temp->next;

		}//while
//----------------------------------------------------

the reason is self explanatory.
u r nt checking for the end of list(Null pointer).

though u should nt mix the 2 kind of variables ,your implementation is nt gona give any
problem ,unless u exhaust all available memory(as u r nt freeing dynamically allocated memory)

Thanks for the responses. Yeah but the assignment doesn't require me to free the dynamically allocated memory. I totally understand that it is the way to go though, thanks again for all the replies. Turned out that I wasn't checking for the end of the list.

Here is my final working code(in case anyone was curious as how I solved the problem):

Code:

#include <iostream>

using namespace std;

struct entry
{
int value;
entry* next;
};

void printList(const entry*);
entry* insert(int n, entry* h);
entry* deleteNode(int n, entry* h);

int main()
{
entry n1, n2, n3, n4, n5, n6, n7, n8, n9, n10;

	n1.value = 2;
	n2.value = 6;
	n3.value = 9;
	n4.value = 13;
	n5.value = 22;
	n6.value = 25;
	n7.value = 30;
	n8.value = 35;
	n9.value = 40;
	n10.value = 50;
	
	n1.next = &n2;
	n2.next = &n3;
	n3.next = &n4;
	n4.next = &n5;
	n5.next = &n6;
	n6.next = &n7;
	n7.next = &n8;
	n8.next = &n9;
	n9.next = &n10;
	n10.next = 0;

	entry* head = &n1;
	
	head = deleteNode(25, head);
	head = deleteNode(50, head);
	head = deleteNode(2, head);

	head = insert(17, head);
	head = insert(75, head);
	head = insert(1, head);

	printList(head);
	return 0;
}//main

/***************************************/

void printList(const entry* pointer)
{
	while(pointer != 0)
	{
		cout << pointer << " " << pointer->value << " " << pointer->next << endl;
		pointer = pointer->next;
	}//while

}//printList

/***************************************/

entry* insert(int n, entry* h)
{
	if(h->value < n)
	{
		entry* prev = h;
		entry* temp = h;

		while(temp->value < n)
		{
			prev = temp;
			temp = temp->next;

			if(temp->next == 0)//if at end of linked list
			{
				temp = new entry;
				prev->next->next = temp;
				temp->value = n;
				temp->next = 0;
				return h;
			}//if
			
		}//while
		temp = new entry;
		temp->value = n;
		temp->next = prev->next;
		prev->next = temp;
		return h;
	}//if
	else// if h->value >= n
	{
		entry* temp = h;

		temp = new entry;
		temp->value = n;
		temp->next = h;
		h = temp;
		return h;
	}//else
	
}//insert

/***************************************/

entry* deleteNode(int n, entry* h)
{
	if(h->value == n)
	{
		h = h->next;
		return h;
	}//if
	else
	{
		entry* prev = h;
		entry* temp = h;

		while(temp->value != n)
		{
			prev = temp;
			temp = temp->next;
		}//while

		prev->next = temp->next;
		return h;
	}//else

}//deleteNode

Originally Posted by swingrohit

the reason is self explanatory.
u r nt checking for the end of list(Null pointer).

though u should nt mix the 2 kind of variables ,your implementation is nt gona give any
problem ,unless u exhaust all available memory(as u r nt freeing dynamically allocated memory)

Welcome newbie !
Please don't use txt speak here. These are web forums, not IRC channels.
Many readers don't have English as their first language, and may not understand you.