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

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.

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

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.

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.

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)

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.

Quote:

---

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.

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?

Quote:

---

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.

Quote:

---

Did you try only printing 2 items instead of 3 after calling delete(anchor) like I suggested?

---

I did. this solved the problem.
Thanx!