Thread: Problem With Inserting into Linked List

  1. #1
    Registered User
    Join Date
    Jul 2007
    Posts
    29

    Question 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!

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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;
        }
      }
    }

  4. #4
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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;
    }
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  5. #5
    Registered User
    Join Date
    Jul 2007
    Posts
    1

    Wink

    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)

  6. #6
    Registered User
    Join Date
    Jul 2007
    Posts
    29
    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

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by swingrohit View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  2. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  3. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM