delete a node from an array of linked lists

This is a discussion on delete a node from an array of linked lists within the C Programming forums, part of the General Programming Boards category; hi there i have an array of linked lists, 10 of them to be precise. insertion works beautifully but deletion ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    delete a node from an array of linked lists

    hi there

    i have an array of linked lists, 10 of them to be precise. insertion works beautifully but deletion is a problem.

    i want a function which returns an int upon deletion. 0 if the node is not in the array or 1 if it is and it was deleted. but, of course, it doesn't work.

    here is my code:

    Code:
    int Delete(node *table[], int key)
    {
    	node *temp, *del;
    	int i;
    	int test = 0;
    		
    	for (i=0; i<10; i++)
    	{
    		temp = table[i];
    		if (temp != NULL)
    		{
    			while (temp->key != key && temp != NULL)
    			{
    				del = temp;
    				temp = temp->next;
    			}
    			
    			if (temp == NULL) continue;	
    			else if (temp->key == key) 
    			{
    					del->next = temp->next;
    					free(temp);
    					test = 1;
    			}
    		}
    		else continue;		
    	}
    	return(test);
    }

  2. #2
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    >>while (temp->key != key && temp != NULL)
    This can cause a seg fault. You need to make it
    while(temp && temp->key != key)
    as to make it short on temp == NULL first.
    Also, if temp == the one you want to delete, you need to save temp, then make the node BEFORE it point to temp->next. This will remove that node from the list, then you can free it. As soon as you free it you should return (unless you are attempting to delete multiple keys from the table -- which would be kinda odd).

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    Nope, still doesn't work! It doesn't delete the node i want when it does exist, but it does return 0 when i try to delete a non-existing node.

    I colored the new lines of code red

    Code:
    int Delete(node *table[], int key)
    {
    	node *temp, *del, *save;
    	int i;
    	int test = 0;
    		
    	for (i=0; i<10; i++)
    	{
    		temp = table[i];
    		if (temp != NULL)
    		{
    			while (temp && temp->key != key)
    			{
    				del = temp;
    				temp = temp->next;
    			}
    			
    			if (temp == NULL) continue;	
    			else if (temp->key == key) 
    			{
    					save =  temp;
    					del->next = temp->next;
    					free(save);
    					test = 1;
    			}
    		}
    		else continue;		
    	}
    	return(test);
    }

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by budala View Post
    Nope, still doesn't work!
    Nobody said that it would work after making those changes. We tend to only each point out some of the things that are wrong. It wont work properly in every case until you've fixed all of the bugs after enough people have contributed.
    Sometimes people are rather generous and spend a lot of their own time finding every bug for you, but don't expect that.

    Okay here's the bugs I've spotted. It will fail if you try and delete the first item for two reasons:
    1. del will be uninitialised when the key of the first item in the list matches because it doesn't enter the while loop.
    2. table[i] is never updated, which it does need to be if you ever delete the first item in the list.

    Again I stress that these are by no means all of the remaining bugs.

    You can delete the "else continue;" line as it is entirely redundant.
    You don't need this line "else if (temp->key == key)" because at that point we know it must match since it will only exit the while loop when the pointer is either NULL or a match was found. If no match was found and it was not null then it would still be back in the loop, looping.
    You also don't really need this line "if (temp != NULL)" because it will work without that, but some people might choose to keep it in there anyway.
    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"

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    I wasn't expecting for all my problems to be solved. The fact that on this forum one doesn't get the code wrapped up in shiny paper is a great plus for me as it is more important to realise why something doesn't work as apart from how it should be written.

    Thanks for your suggestions iMalc and to you Kennedy too, I re-did my code and now it works as expected:

    Code:
    int Delete(node *table[], int key)
    {
    	node *temp, *del;
    	int i;
    	int test = 0;
    		
    	for (i=0; i<10; i++)
    	{
    		temp = table[i];
    		if (temp != NULL)
    		{
    			if (temp->key == key)
    			{
    				table[i] = temp->next;
    				free(temp);
    				test++;
    			}
    			else
    			{
    				while (temp && temp->key != key)
    				{
    					del = temp;
    					temp = temp->next;
    				}
    
    				if (temp)
    				{
    					del->next = temp->next;
    					free(temp);
    					test ++;
    				}
    			}
    		}		
    	}
    	return(test);
    }

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Ah, that looks good now.

    I noticed that it will return how many items it found and removed, rather than only returning one or zero. It looks like this is what you wanted though and simply didn't go into that much detail in your description.
    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"

  7. #7
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    I guess I could/should have included a break in the for loop after it finds the sought node

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Delete Function in Doubly Linked List
    By Dampecram in forum C Programming
    Replies: 5
    Last Post: 11-15-2008, 03:30 PM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21