Delete element from doubly linked list using recursive

Question

I want to delete an element from doubly linked list, but i need to using recursion. I write function but it doesn't work. Can someone tell me where did i a mistake?

int deleteNode(struct dll_node **front, int data){
    if((*front) == NULL){
        return 0;
    }

    if(data == (*front)->data){
        int tmp = (*front)->data;
        (*front)->next = (*front)->prev;
        (*front)->prev = (*front)->next;
        free(*front);
        return tmp;
    }
    deleteNode((*front)->next, data);
}

Answer 1

there are several problems

• you save data in tmp for nothing
• you do not update rightly the list
• your recursive call does not give right the first argument (must be deleteNode(&(*front)->next, data);, and in fact you must return it), note it is terminal so you can also use a loop
• return is missing if the two tests are false

It can be :

int deleteNode(struct dll_node **front, int data){
  if((*front) == NULL){
    return 0;
  }

  if(data == (*front)->data){
    struct dll_node * d = *front;

    if (d->prev == NULL) {
      if ((*front = d->next) != NULL)
        (*front)->prev = NULL;
    }
    else if ((d->prev->next = d->next) != NULL)
      d->next->prev = d->prev;

    free(d);
    return data;
  }
  return deleteNode(&(*front)->next, data);
}

---

Full code to check :

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

struct dll_node {
  int data;
  struct dll_node * prev;
  struct dll_node * next;
};

int deleteNode(struct dll_node **front, int data){
  if((*front) == NULL){
    return 0;
  }

  if(data == (*front)->data){
    struct dll_node * d = *front;

    if (d->prev == NULL) {
      if ((*front = d->next) != NULL)
        (*front)->prev = NULL;
    }
    else if ((d->prev->next = d->next) != NULL)
      d->next->prev = d->prev;

    free(d);
    return data;
  }
  return deleteNode(&(*front)->next, data);
}

struct dll_node * mk(int d)
{
  struct dll_node * r = malloc(sizeof(struct dll_node));

  r->data = d;
  r->prev = NULL;
  r->next = NULL;

  return r;
}

void pr(struct dll_node * l)
{
  while (l != NULL) {
    printf("%d", l->data);
    if (l->prev)
      printf(" prev:%d\n", l->prev->data);
    else
      putchar('\n');
    l = l->next;
  }
}

int main()
{
  struct dll_node * head = mk(1);
  struct dll_node * a = mk(2);
  struct dll_node * b = mk(3);

  head->next = a;
  a->prev = head;

  b->prev = a;
  a->next = b;

  pr(head);

  puts("\ndel 3");
  deleteNode(&head, 3);
  pr(head);

  puts("\ndel 1");
  deleteNode(&head, 1);
  pr(head);

  puts("\ndel 2");
  deleteNode(&head, 2);
  pr(head);
}

Compilation and executions :

pi@raspberrypi:/tmp $ gcc -Wall l.c
pi@raspberrypi:/tmp $ ./a.out
1
2 prev:1
3 prev:2

del 3
1
2 prev:1

del 1
2

del 2
pi@raspberrypi:/tmp $ valgrind ./a.out
==8496== Memcheck, a memory error detector
==8496== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==8496== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==8496== Command: ./a.out
==8496== 
1
2 prev:1
3 prev:2

del 3
1
2 prev:1

del 1
2

del 2
==8496== 
==8496== HEAP SUMMARY:
==8496==     in use at exit: 0 bytes in 0 blocks
==8496==   total heap usage: 4 allocs, 4 frees, 1,060 bytes allocated
==8496== 
==8496== All heap blocks were freed -- no leaks are possible
==8496== 
==8496== For lists of detected and suppressed errors, rerun with: -s
==8496== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $