Thread: delete node in Linked List

  1. #1
    Registered User
    Join Date
    Jun 2004
    Posts
    123

    delete node in Linked List

    This function is deleting a node from linked list. It is OK with nodes which are not the first node. When I send anchor to function, I lose the link to the rest of the list. Why is it so?


    Code:
    void delete(visit_ptr_node_type this_is_the_node)
    {
      visit_ptr_node_type one_back;
      if(anchor == NULL)
        printf("\n The list is empty");
      else
        {
        if(this_is_the_node==anchor)
          anchor=anchor->next_ptr;
        else
          {
          one_back=anchor;
          while(one_back->next_ptr != this_is_the_node)
    	one_back=one_back->next_ptr;
          one_back->next_ptr = (this_is_the_node) ->next_ptr;
          }
        free(this_is_the_node);
        }
    }
    TIA,
    Ronen

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Are you sure it's not in the way you're calling delete()? The function you showed looks ok to me. I'm assuming anchor is a global variable.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    This is my full code:
    Code:
    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct visit_node
      {
        char v_name;
        struct visit_node *next_ptr;
      }
    visit_node_type, *visit_ptr_node_type;
    
    visit_ptr_node_type anchor;
    
    
    void insert_after(visit_ptr_node_type after_this_node, visit_ptr_node_type new_node)
    {
      if(anchor==NULL)
        {
        new_node->next_ptr=NULL;
        anchor=new_node;
        }
      else
        {
        new_node->next_ptr=after_this_node->next_ptr;
        after_this_node->next_ptr=new_node;
        }
    }
    
    void delete(visit_ptr_node_type this_is_the_node)
    {
      visit_ptr_node_type one_back;
      if(anchor == NULL)
        printf("\n The list is empty");
      else
        {
        if(this_is_the_node==anchor)
          anchor=anchor->next_ptr;
        else
          {
          one_back=anchor;
          while(one_back->next_ptr != this_is_the_node)
    	one_back=one_back->next_ptr;
          one_back->next_ptr = (this_is_the_node) ->next_ptr;
          }
        free(this_is_the_node);
        }
    }
    
    main()
    { 
      visit_ptr_node_type p1,p2;
      visit_ptr_node_type hadash;
    
      anchor=(visit_ptr_node_type)malloc(sizeof(visit_node_type));
      p1=(visit_ptr_node_type)malloc(sizeof(visit_node_type));
      p2=(visit_ptr_node_type)malloc(sizeof(visit_node_type));
    
      anchor->v_name ='A';
      p1->v_name='I';
      p2->v_name='Y';
    
      anchor->next_ptr=p1;
      p1->next_ptr=p2;
      p2->next_ptr=NULL;
    
    //  clrscr();
      printf("\n FIRST LIST");
      printf("\n The characters in the list are :");
      printf("\n first= %c second= %c third= %c\n",anchor->v_name,
    	anchor->next_ptr->v_name,anchor->next_ptr->next_ptr->v_name);
      hadash=malloc(sizeof(visit_node_type));
      hadash->v_name='N';
      printf("\n Insert the char N after the char I");
      insert_after(p1,hadash);
      printf("\n The characters in the list are :");
      printf("\n first= %c second= %c third= %c fourth= %c\n",anchor->v_name,
    	 anchor->next_ptr->v_name,anchor->next_ptr->next_ptr->v_name,
    	 anchor->next_ptr->next_ptr->next_ptr->v_name);
      printf("\n Delete the char I from the list");
      delete(p1);
      printf("\n The characters in the list are :");
      printf("\n first= %c second= %c third= %c\n",anchor->v_name,
    	 anchor->next_ptr->v_name,anchor->next_ptr->next_ptr->v_name);
      printf("\n Delete the first char A {anchor} from the list");
      delete(anchor);
      printf("\n The characters in the list are :");
      printf("\n first= %c second= %c third= %c\n",anchor->v_name,
    	 anchor->next_ptr->v_name,anchor->next_ptr->next_ptr->v_name);
      printf("\n THE SECOND LIST IS EMPTY");
      anchor=NULL;
      printf("\n Delete one char from the empty list");
      delete(anchor);
      printf("\n \n Insert the char N into the empty list:");
      insert_after(anchor,hadash);
      printf("\n The characters in the list are : first= %c",anchor->v_name);
    }
    If I send anchor to function as a pointer (&anchor), then also the nodes in the middle don't get deleted (p1).


    Ronen

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    And now you know why double linked lists are so much better. Want to delete a node? With only that node?
    Code:
    struct Node *list;
    ...
    delete( thisnode );
    ...
    void delete( struct Node *n )
    {
        if( n->prev )
            n->prev->next = n->next;
        if( n->next )
            n->next->prev = n->prev;
        if( n == list )
            list = n->next;
        free( n );
    }
    Other than that, I hate hidden pointers with a passion, and refuse to read code which contains them.

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

  5. #5
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Aside from other things, I see that you have you 3 items in the list after calling delete(p1)

    Then you call delete(anchor) and try printing 3 items again. This should give you a segfault since you'll end up dereferencing a NULL pointer.
    If you understand what you're doing, you're not learning anything.

  6. #6
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Here you go Quzah:
    Code:
    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct visit_node
    {
      char v_name;
      struct visit_node *next;
    } NODE;
    
    NODE *anchor;
    
    void insert_after(NODE *after, NODE *new)
    {
      if(!anchor)
      {
        new->next = NULL;
        anchor = new;
      }
      else
      {
        new->next = after->next;
        after->next = new;
      }
    }
    
    void delete(NODE *node)
    {
      NODE *one_back;
    
      if(!anchor)
        printf("\n The list is empty");
      else
      {
        if(node == anchor)
          anchor = anchor->next;
        else
        {
          one_back = anchor;
          while(one_back->next != node)
            one_back = one_back->next;
          one_back->next = node->next;
        }
    
        free(node);
      }
    }
    
    int main(void)
    {
      NODE *p1, *p2;
      NODE *hadash;
    
      anchor = malloc(sizeof(NODE));
      p1 = malloc(sizeof(NODE));
      p2 = malloc(sizeof(NODE));
    
      anchor->v_name = 'A';
      p1->v_name = 'I';
      p2->v_name = 'Y';
    
      anchor->next = p1;
      p1->next = p2;
      p2->next = NULL;
    
      printf("\n FIRST LIST");
      printf("\n The characters in the list are :");
      printf("\n first= %c second= %c third= %c\n", anchor->v_name,
        anchor->next->v_name, anchor->next->next->v_name);
    
      hadash = malloc(sizeof(NODE));
      hadash->v_name = 'N';
      printf("\n Insert the char N after the char I");
      insert_after(p1, hadash);
      printf("\n The characters in the list are :");
      printf("\n first= %c second= %c third= %c fourth= %c\n",
        anchor->v_name, anchor->next->v_name, anchor->next->next->v_name,
        anchor->next->next->next->v_name);
    
      printf("\n Delete the char I from the list");
      delete(p1);
      printf("\n The characters in the list are :");
      printf("\n first= %c second= %c third= %c\n", anchor->v_name,
        anchor->next->v_name, anchor->next->next->v_name);
    
      printf("\n Delete the first char A {anchor} from the list");
      delete(anchor);
      printf("\n The characters in the list are :");
      printf("\n first= %c second= %c third= %c\n", anchor->v_name,
        anchor->next->v_name, anchor->next->next->v_name);
    
      printf("\n THE SECOND LIST IS EMPTY");
      anchor = NULL;
      printf("\n Delete one char from the empty list");
      delete(anchor);
    
      printf("\n \n Insert the char N into the empty list:");
      insert_after(anchor, hadash);
      printf("\n The characters in the list are : first= %c",
        anchor->v_name);
    
      return 0;
    }
    I had to clean it up so I could read it (and it's still pretty bad)
    If you understand what you're doing, you're not learning anything.

  7. #7
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    Other then changing variables names I don't see any significant change in the code above. The output is left the same; I still seem to lose the link to the list.

    Other than that, I hate hidden pointers with a passion, and refuse to read code which contains them.
    Quzah, what are hidden pointers with a passion? I honestly don't understand this phrase.

  8. #8
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    You have a visit_ptr_node_type which is really just a visit_node_type *

    The visit_ptr_node_type is what he's talking about. You'll notice that in my restructured code I don't hide pointers behind a typedef.

    And you're right about changing some variable names but not doing anything significant. My goal was to make your code more readable without changing its functionality. If I changed the way it works then I couldn't be much help to you in solving your problem.

    I didn't fix the problem in the code I posted. I just posted a "more readable" version of your code (to me anyway). I explained what your problem is though. You shouldn't be losing your list, you should be getting a segfault. Did you try only printing 2 items instead of 3 after calling delete(anchor) like I suggested?
    If you understand what you're doing, you're not learning anything.

  9. #9
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    I didn't fix the problem in the code I posted. I just posted a "more readable" version of your code (to me anyway).
    Ok, now I see your point.

    Did you try only printing 2 items instead of 3 after calling delete(anchor) like I suggested?
    I did. this solved the problem.
    Thanx!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 12-06-2008, 07:54 PM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. Replies: 7
    Last Post: 06-16-2006, 09:23 PM
  5. Help here with qsort!
    By xxxrugby in forum C Programming
    Replies: 11
    Last Post: 02-09-2005, 08:52 AM