CODEWITHSUNDEEP
calgorithmrecursionlinked-list
LEARNER
LEARNER

Reputation: 123

Delete all occurrences of a number in a linked list using recursion

I wanted to write a program that removes all occurrences of a number from a simple linked list using recursion, so I tried but I had problem: the program that I have written erases all the occurrences in the list but it does not delete the one that exists at the beginning (the occurrence that exists at the first node), here is the code in C:

typedef struct list {
    int data;
    struct list *next;
} list;

list *delete(int x, list *head) {
    if (head->next == NULL)
        return head;
    list *newnode = delete(x, head->next);
    if (newnode->data == x) {
        head->next = head->next->next;
        free(newnode);
    }
    return head;
}

I wish someone can help me to improve my algorithm, THANKS IN ADVANCE.

Upvotes: 2

Views: 1501

Answers (3)

bruno
bruno

Reputation: 32586

without it manages to delete the one that exists at the beginning (the occurrence that exists at the first node),

this is because of these lines :

   if(head->next == NULL)
       return head;

when there is only one element you return without managing the fact it can contains the data to remove

You do not need to have a recursive definition of delete, and worst using non terminal recursion.

Can be also adding working functions to check the execution :

#include <stdio.h>
#include <stdlib.h>

typedef struct list {
  int data;
  struct list* next;
} list;

list* delete(int x, list* head)
{
  list ** p = &head;

  while (*p != NULL) {
    if ((*p)->data == x) {
      list * d = *p;

      *p = (*p)->next;
      free(d);
    }
    else
      p = &(*p)->next;
  }
  return head;
}

void print(list * l)
{
  if (l == NULL)
    puts("<empty>");
  else {
    do  {
      printf("%d ", l->data);
      l = l->next;
    } while (l != NULL);
    putchar('\n');
  }
}

list * make(int data, list * next)
{
  list * l = malloc(sizeof(list));

  l->data = data;
  l->next = next;
  return l;
}

int main(int argc, char ** argv)
{
  list * head = make(1, make(2, make(1, NULL)));

  print(head);
  head = delete(1, head);
  print(head);
  head = delete(2, head);
  print(head);

  return 0;
}

Compilation and execution:

/tmp % gcc -Wall l.c
/tmp % ./a.out
1 2 1 
2 
<empty>
/tmp %

Under valgrind :

/tmp % valgrind ./a.out                                                                    ==14732== Memcheck, a memory error detector
==14732== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==14732== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==14732== Command: ./a.out
==14732== 
1 2 1 
2 
<empty>
==14732== 
==14732== HEAP SUMMARY:
==14732==     in use at exit: 0 bytes in 0 blocks
==14732==   total heap usage: 3 allocs, 3 frees, 48 bytes allocated
==14732== 
==14732== All heap blocks were freed -- no leaks are possible
==14732== 
==14732== For counts of detected and suppressed errors, rerun with: -v
==14732== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
/tmp %

Upvotes: 2

chqrlie
chqrlie

Reputation: 144715

There are multiple problems in the code:

  • You dereference head without first checking if it is NULL. The function cannot handle empty lists.
  • You explicitly return the head node without testing its value if the list has a single element.
  • You only test the second element of the list after recursing on head->next. Hence the first element is never tested.

Here is a modified version that just tests the first node and recurses for the rest of the list:

list *delete(int x, list *head) {
    if (head == NULL)
        return head;
    if (head->data == x) {
        list *node = head;
        head = head->next;
        free(node);
        return delete(x, head);
    }
    head->next = delete(x, head->next);
    return head;
}

Upvotes: 2

unwind
unwind

Reputation: 399803

This code:

    if(head->next == NULL)
        return head;

explicitly makes the function return any 1-element list unchanged. That creates the problem you describe, so that makes no sense to have there.

I guess it should be possible to formulate the deletion of a list element recursively, although it certainly is not a common/typical/good way to do it.

This might work, not tested:

list * delete(list *head, int value)
{
  if (head == NULL)
    return NULL;
  if (head->data == value)
  {
      list * tail = head->next;
      free(head);
      return delete(tail, value);
  }
  // List was not empty and did not start with the value,
  // so set the tail of the list to the tail without the value.
  head->next = delete(head->next, value);
  return head;
}

Upvotes: 2

Related Questions