MHB How to Properly Implement the Delete() Algorithm for Linked Lists

[evinda]

Hello! (Smile)

I want to implement the algorithm [m]Delete()[/m] for linked lists.
That's what I have tried:

void Delete(pointer L,Type x){
      if (L==NULL){
         printf("There is no element x in the list. \n");
         return;
      }
      pointer q=L;
      while (q!=NULL && q->next->data!=x)
               q=q->next;
      q->next=q->next->next;
}

Could you tell me if it is right or if I have done something wrong? (Thinking)

 

[I like Serena]

1. void Delete(pointer L,Type x){
2.      if (L==NULL){
3.         printf("There is no element x in the list. \n");
4.         return;
5.      }
6.      pointer q=L;
7.      while (q!=NULL && q->next->data!=x)
8.               q=q->next;
9.      q->next=q->next->next;
}

Hi! (Happy)

In line 7, there should be a check if [m]q->next[/m] is NULL before dereferencing it. (Worried)
The check [m]q!=NULL[/m] is redundant then.In line 9, you are assuming you have found x, but that is not necessarily the case.
It may still be that x is not in the list. (Doh)In line 9 you are indeed removing the element that [m]q->next[/m] point to from the list (if it was found).
However, usually this memory has to be released with [m]free()[/m]. (Sweating)

 

[evinda]

Hi! (Happy)

In line 7, there should be a check if [m]q->next[/m] is NULL before dereferencing it. (Worried)
The check [m]q!=NULL[/m] is redundant then.In line 9, you are assuming you have found x, but that is not necessarily the case.
It may still be that x is not in the list. (Doh)In line 9 you are indeed removing the element that [m]q->next[/m] point to from the list (if it was found).

So, should it be like that? (Thinking)

1. void Delete(pointer L,Type x){
2.      if (L==NULL){
3.         printf("There list is empty. \n");
4.         return;
5.      }
6.      pointer q=L;
7.      while (q->next!=NULL && q->next->data!=x)
8.               q=q->next;
9.      if (q->next->data==x)   q->next=q->next->next;
10.         else printf("There is no element x in the list. \n");
}

However, usually this memory has to be released with [m]free()[/m]. (Sweating)

How can this memory be released with [m]free()[/m]? (Thinking)

 

[I like Serena]

So, should it be like that? (Thinking)

1. void Delete(pointer L,Type x){
2.      if (L==NULL){
3.         printf("There list is empty. \n");
4.         return;
5.      }
6.      pointer q=L;
7.      while (q->next!=NULL && q->next->data!=x)
8.               q=q->next;
9.      if (q->next->data==x)   q->next=q->next->next;
10.         else printf("There is no element x in the list. \n");
}

If x could not be found, q->next will end up as NULL.
Then line 9 will cause some chaos and madness. (Worried)

There is another issue.
Suppose that x is the very first element in the list, what will happen then? (Wondering)

How can this memory be released with [m]free()[/m]? (Thinking)

With something like:

if (q->next->data==x) {
    free(q->next);
    q->next=q->next->next;
}

This assumes the node was originally allocated with malloc() or calloc(). (Wasntme)

 

[kaliprasad]

If x could not be found, q->next will end up as NULL.
Then line 9 will cause some chaos and madness. (Worried)

There is another issue.
Suppose that x is the very first element in the list, what will happen then? (Wondering)

With something like:

if (q->next->data==x) {
    free(q->next);
    q->next=q->next->next;
}

This assumes the node was originally allocated with malloc() or calloc(). (Wasntme)

the code
if (q->next->data==x) {
free(q->next);
q->next=q->next->next;
}is dangerous coding as we have freed q->next we cannot use q->next-> next and need to be replaced by

if (q->next->data==x) {
pointer p = q->next->next;
free(q->next);
q->next=p;
}

 

[evinda]

If x could not be found, q->next will end up as NULL.
Then line 9 will cause some chaos and madness. (Worried)

There is another issue.
Suppose that x is the very first element in the list, what will happen then? (Wondering)

1. void Delete(pointer L,Type x){
2.      if (L==NULL){
3.         printf("There list is empty. \n");
4.         return;
5.      }
6.      pointer q=L;
7.      if (q->data==x){
8.            q=q->next;
9.            return;
10.     while (q->next!=NULL && q->next->data!=x)
11.              q=q->next;
12.     if (q->next->data==x)&&(q->next->next!=NULL)   q->next=q->next->next;
13.      else if  (q->next->data==x)   
14.      else printf("The element x does not exist. \n")
}

So, should it be like that? (Thinking) If so, what could we do in line 13?

 

[I like Serena]

1. void Delete(pointer L,Type x){
2.      if (L==NULL){
3.         printf("There list is empty. \n");
4.         return;
5.      }
6.      pointer q=L;
7.      if (q->data==x){
8.            q=q->next;
9.            return;
10.     while (q->next!=NULL && q->next->data!=x)
11.              q=q->next;
12.     if (q->next->data==x)&&(q->next->next!=NULL)   q->next=q->next->next;
13.      else if  (q->next->data==x)   
14.      else printf("The element x does not exist. \n")
}

So, should it be like that? (Thinking) If so, what could we do in line 13?

I'm afraid there are a couple more issues. (Sweating)

In line 8 you are changing [m]q[/m]. However, that will not be enough. [m]L[/m] will need to be changed - and not only here, but effectively also in the caller. (Worried)

Line 12 is not quite right yet.
Note that when the while-loop in line 10 finishes without finding x, we will have q->next==NULL. That means that line 12 will fail, not to mention line 13. (Doh)

 

[evinda]

I tried it again... Do I have to change something ? (Thinking)

Delete(pointer L, Type x){
  if (L==NULL){
     printf("The list is empty. \n");
     return;
  }
  q=L;
  if (q->data==x){
      q=q->next;
      L=q;
      return;
  }
  while (q->next!=NULL and q->next->data!=x) q=q->next;
  if (q->next==NULL){
     printf("There isn't an element of which the value is equal to %d\n",x);
     return;
  }
  if (q->next->data==x){
      q=q->next->next;
      L=q;
  }