Thread: deleting a node in linked list

  1. #1
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62

    deleting a node in linked list

    I have a program that gives me this output:
    Code:
    Enter (+) integers and terminate it by 0
    1
    2
    3
    0
    The list is: 1 2 3 
    
    3 items were entered to the list
    Sum of the items are: 6
    Enter a integer to check is it in the list:2
    2 is in the list
    The list is: 1 2 3 
    Enter a number to delete it from the list:2
    The list is modified
    The list is: 1 0 3
    the problem is when i wanted to delete a node, it deletes it but replaces with O. I try to point the node after the node that I want to delete and after that remove the node.But I couldn't make it.

    This is the function:
    Code:
    /*Function to delete a specific number from the list*/
    void delete(int n, node_ptr list)
    {
    	node_ptr tmp;
    	node_ptr current = list->next;
    	int number;
    	
    	printf("Enter a number to delete it from the list:");
    	scanf("\n%d",&number);
    	
    	while(current != NULL)
    	{
    		if(current->data_item == number)
    		{
    			tmp = current->next;
    			free (current);
    			current = tmp;
    			printf("The list is modified\n");
    			break;
    		}
    		else
    		{
    			current = current->next;
    		}
    	}
    	if(current == NULL )
    	{
    		printf("%d is not in the list\n", number);
    	}
    	return;
    this is the all code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "1.h"
    
    /*Function to create an empty List*/
    node_ptr create(void)
    {
    	node_ptr list=(node_ptr)malloc(sizeof(struct node));
    	list->data_item = 0;/*The first node*/
    	list->next = NULL; /*the last node*/
    	return list;
    }
    /*Function to return dynamically allocated memory in list*/
    void destroy(node_ptr list)
    {
    	node_ptr current = list;
    	
    	while(current)
    	{
    		node_ptr to_free = current;
    		current = current -> next;
    		free(to_free);
    	}
    }
    /*Function to insert n at front of list*/
    void insert_at_front(int n, node_ptr list)
    {
    	node_ptr new_node= (node_ptr)malloc(sizeof(struct node));
    	new_node -> data_item = n;
    	new_node -> next = list-> next;
    	list -> next = new_node; 
    }
    /*Function to print list*/
    void print(node_ptr list)
    {
    	node_ptr current = list -> next;
    	printf("The list is: ");
    	while(current)
    	{
    		printf("%d ", current->data_item);
    		current = current->next;
    	}
    	printf("\n");
    }
    /*Function  to insert n in  ( non decreasing ) order in list - assuming list items are already in ( non decreasing ) order. */
    void insert_in_order(int n, node_ptr list)
    {
    	node_ptr before = list;
    	node_ptr new_node = (node_ptr) malloc(sizeof(struct node));
    	new_node-> data_item = n;
    	
    	while(before-> next && (before->next->data_item < n))
    	{
    		before = before->next;
    	}
    	new_node->next = before-> next;
    	before->next = new_node;
    }
    /*Function  to find the number of items in the list*/
    int length(node_ptr list)
    {
    	node_ptr current = list->next;
    	int r = 0;
    	while(current)
    	{
    		r++;
    		current = current->next;
    	}
    	printf("\n%d items were entered to the list", r);
    	return r;
    }
    /*Function to sum the integer values in the list*/
    int sum(node_ptr list)
    {
    	node_ptr current = list->next;
    	int t = 0;
    	while(current)
    	{
    		t = t + current->data_item;
    		current = current->next;
    	}
    	printf("\nSum of the items are: %d\n", t);
    	return t;
    }
    /*Function to find a specific number in the list*/
    node_ptr find(int n, node_ptr list)
    {
    	node_ptr current = list->next;
    	int number=0;
    	
    	printf("Enter a integer to check is it in the list:");
    	scanf("\n%d",&number);
    		
    	while(current != NULL)
    	{
    		if(current->data_item == number)
    		{
    			printf("%d is in the list\n", number);
    			break;
    		}
    		else
    		{
    			current = current->next;
    		}
    	}
    	if(current == NULL)
    	{
    		printf("%d is not in the list\n", number);
    	}
    	return current;
    }
    /*Function to delete a specific number from the list*/
    void delete(int n, node_ptr list)
    {
    	node_ptr tmp;
    	node_ptr current = list->next;
    	int number;
    	
    	printf("Enter a number to delete it from the list:");
    	scanf("\n%d",&number);
    	
    	while(current != NULL)
    	{
    		if(current->data_item == number)
    		{
    			tmp = current->next;
    			free (current);
    			current = tmp;
    			printf("The list is modified\n");
    			break;
    		}
    		else
    		{
    			current = current->next;
    		}
    	}
    	if(current == NULL )
    	{
    		printf("%d is not in the list\n", number);
    	}
    	return;
    }
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    tmp = current->next;
    free (current);
    current = tmp;
    You just freed current, now you make it point to the next element again.

    Hint, you need to link the previous node before current to current->next.

  3. #3
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Quote Originally Posted by anon View Post
    Code:
    tmp = current->next;
    free (current);
    current = tmp;
    You just freed current, now you make it point to the next element again.

    Hint, you need to link the previous node before current to current->next.
    Code:
    node_ptr before = list;
    before -> next = current-> next;
    current = before -> next;
    free(current);
    now I get just 0 when I print out the list. nothing lefts in the list.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I think you might try something like this:
    Code:
    Node* current = first;
    Node* previous = NULL;
    while (current != NULL) {
        //...
        previous = current;
        current = current->next;
    }
    At any point you need to have a pointer to the previous node. Also note that you can erase the first node, in which case there is no previous node and current->next becomes the new head.

  5. #5
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    I am sorry u helped lot but I just couldn't make it. When I try to understand more I started to confuse more:

    Code:
    void delete(int n, node_ptr list)
    {
    	node_ptr previous = NULL;
    	node_ptr current = list->next;
    	int number;
    	
    	printf("Enter a number to delete it from the list:");
    	scanf("\n&#37;d",&number);
    	
    	while(current != NULL)
    	{
    		if(current->data_item == number && previous->next->data_item != 0)
    		{
    			previous = current;
    			previous -> next = (current->next)->next;
    			current = current -> next;
    			free(current);
    			printf("The list is modified\n");
    			break;
    		}
    		else
    		{
    			current = current->next;
    		}
    	}
    	if(current == NULL )
    	{
    		printf("%d is not in the list\n", number);
    	}
    	return;
    }
    This is the last point I came, when I look to codes I say "this should be right!" but unfortunately output doesn't agree with me,and it says

    Code:
    Enter (+) integers and terminate it by 0
    1
    2
    3
    0
    The list is: 1 2 3 
    
    3 items were entered to the list
    Sum of the items are: 6
    Enter a integer to check is it in the list:3
    3 is in the list
    The list is: 1 2 3 
    Enter a number to delete it from the list:3
    Segmentation fault
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    1 links to 2 links to 3

    If you want to remove 2, what must happen?

    1 links to 3

    You therefore must have a pointer pointing to the node before the one you're considering for removal, so you can make that node point to the one after the one you're going to remove.


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Quote Originally Posted by quzah View Post
    1 links to 2 links to 3

    If you want to remove 2, what must happen?

    1 links to 3

    You therefore must have a pointer pointing to the node before the one you're considering for removal, so you can make that node point to the one after the one you're going to remove.


    Quzah.
    I know and trying to do that last 2 days, but couldn't make it. But I didn't give up(yet)
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    foo *prev = NULL, *curr = list;
    while( curr )
    {
        ... check to see if this is what you need...
            ... handle appropriately ...
    
        ... fix up your pointers ...
        prev = curr;
        curr = curr->next;
    }
    Just like anon showed you earlier.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    The thing that I don't understand is:

    For example the list is 1 2 3 4 and I want to delete 3.

    When the program is searching to find the integer to delete( by while loop) it passes 2 and it comes to 3 then bingo current is 3 the program found it, and in that stage current-> next is 4.

    So , I want to link 2 to the 4 and free the node where the 3 is. But the thing that I don't get, I don't know how will I go back to 2 and link it to the 4. Because I already passed the value 2.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You "go back" to two by having a pointer pointing to the previous node. Just like how you use one to track "current", you have another one that is tracking "curren - 1". That is to say, it's trailing one loop behind. You've been shown twice how to do it.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Mar 2005
    Posts
    37
    Quote Originally Posted by BoneXXX View Post
    The thing that I don't understand is:

    For example the list is 1 2 3 4 and I want to delete 3.

    When the program is searching to find the integer to delete( by while loop) it passes 2 and it comes to 3 then bingo current is 3 the program found it, and in that stage current-> next is 4.

    So , I want to link 2 to the 4 and free the node where the 3 is. But the thing that I don't get, I don't know how will I go back to 2 and link it to the 4. Because I already passed the value 2.
    what you can do is have 3 nodes call them , prev , current, nex . prev node will be before Current and nex will be the node after current.

    in your example, 2 will be held by prev, 3 will be held by current and 4 will be held by nex .

    now all you have to do is prev->next= nex ; and free (current).

    Happy hacking.. ;-)

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You don't need a next node because you already have it as a member of the curr node itself.


    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Sorry guys I had problem with my internet connection and couldn't reply you, I solved the problem(of course with your helps). Thanks

    Code:
    void delete(int n, node_ptr list)
    {
    	node_ptr previous = list;
    	node_ptr current = list->next;
    	
    	printf("Enter a number to delete it from the list:");
    	scanf("\n%d",&n);
    	
    	while(current != NULL)
    	{
    		if(current->data_item == n)
    		{
    			previous->next = current->next;
    			free(current);
    			printf("The list is modified\n");
    			break;
    		}
    		else
    		{
    			previous = current;
    			current = current->next;
    		}
    	}
    	if(current == NULL )
    	{
    		printf("%d is not in the list\n", n);
    	}
    	return;
    }
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If the node is the first one in the list, your code won't remove it because you're starting looking at "list->next" as current. Also, if a NULL is passed as the list to your function, your assignment to "current" at the start will crash it when you try to access "list->next".


    Quzah.
    Hope is the first step on the road to disappointment.

  15. #15
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Actually I thought that too, But it perfectly ran with simple 1,2,3 linked list. I deleted all the nodes one by one and no problemo. i ll try it again.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. Problems with deleting a node in a singly linked list
    By omishompi in forum C++ Programming
    Replies: 7
    Last Post: 02-23-2006, 06:27 PM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM