CODEWITHSUNDEEP
crecursionlinked-list
Hanfu
Hanfu

Reputation: 35

Delete single linked list recursively in C

It looks there is no duplicate questions...so i want a function to free all nodes in a single linked list, and i want to do it recursively. I come up with a close one that i thought it would work, but it does not. It seems that after it removed one node, the upper stack function will not excuse, recursively. I am wondering how to modify the code to make it work.

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

struct Node 
{
  int data;
  struct Node *next;
};

void ft_list_clear(struct Node *begin_list)
{
    if ((begin_list->next))
      ft_list_clear(begin_list->next);
    if(!(begin_list->next))
    {
      free(begin_list);
      begin_list = NULL;
    }
}

int main()
{
  struct Node* head = NULL;
  struct Node* second = NULL;
  struct Node* third = NULL;

  // allocate 3 nodes in the heap  
  head  = (struct Node*)malloc(sizeof(struct Node)); 
  second = (struct Node*)malloc(sizeof(struct Node));
  third  = (struct Node*)malloc(sizeof(struct Node));

  head->data = 1; //assign data in first node
  head->next = second; // Link first node with second   

  second->data = 2; //assign data to second node
  second->next = third;  

  third->data = 3; //assign data to third node
  third->next = NULL;

  ft_list_clear(head);
  return 0;
}

Upvotes: 0

Views: 1955

Answers (5)

ChuckCottrill
ChuckCottrill

Reputation: 4444

Recursively deleting a linked is a bad idea. Each recursive call requires a stack frame, and whether you free the list node memory as you descend or ascend the recursion, you need O(n) memory for what is a simple operation. Each stack call requires local variable storage, room for return pointer, previous stack frame pointer, and possibly other stuff (at least 12-24 bytes per node).

Better to iterate through the list. I have provided three variants of the free (iterative, and two recursive, one free's node on descent, one free's node on ascent).

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

typedef struct Node 
{
    int data;
    struct Node* next;
} node_t;

long list_clear_iter(node_t* p) {
    if(!p) return 0;
    long n = 0; //count;
    for( ; p->next; ) {
        node_t* fp = p; //free this
        p = p->next;
        free(fp);
        ++n;
    }
    return n;
}

//list clear, recursive, (pre)free
long ft_list_clear_pr(node_t* p) {
    if(!p) return 0;
    node_t* np = p->next;
    free(p); //free on descend
    long n = ft_list_clear_pr(np);
    return(n+1);
}
//list clear recursive, free(post)
long ft_list_clear_rp(node_t* p) {
    if(!p) return 0;
    long n = ft_list_clear_rp(p->next);
    free(p); //free on ascend
    return(n+1);
}

Upvotes: 0

Pablo
Pablo

Reputation: 13580

The problem with this

void ft_list_clear(struct Node *begin_list)
{
    if ((begin_list->next))
      ft_list_clear(begin_list->next);
    if(!(begin_list->next))
    {
      free(begin_list);
      begin_list = NULL;
    }
}

is:

  • In the first call, begin_list is equal to head.
  • head->next is not NULL, so ft_list_clear(second) is executed
  • second->next is not NULL, so ft_list_clear(third) is executed
  • third->next is NULL, so free(third) happens. The begin_list = NULL line does nothing here, its pointless.

  • The third iteration returns, back to the second. The next line to execute is

    if(!(begin_list->next))

    begin_list->next is not NULL (it's been only freed), hence the condition is evaluated to false and the free is not executed.

  • Same happens with the first iteration.

This is recursion that would work:

void ft_list_clear(struct Node *begin_list)
{
    if(begin_list == NULL)
        return;

    ft_list_clear(begin_list->next);
    free(begin_list);
}

Upvotes: 1

Wreigh
Wreigh

Reputation: 3287

I think it's because you're just freeing nodes, but you miss to nullify the next members. Try this. I haven't run this so goodluck. 

void ft_list_clear(struct Node *begin_list)
{
    if ((begin_list->next))
    {
      ft_list_clear(begin_list->next);
      begin_list->next = NULL; // <-- you should nullify the next of the current after you free the node which it points to.
    }
    if(!(begin_list->next)) // <-- even if the next node was deleted, this won't run if you didn't nullify begin_list->next
    {
      free(begin_list);
      begin_list = NULL;
    }
}

Upvotes: 1

Naman Chikara
Naman Chikara

Reputation: 174

`void ft_list_clear(struct Node *begin_list)

{
    if ((begin_list->next))
      ft_list_clear(begin_list->next);

    free(begin_list);
    begin_list = NULL;
    printf("God bless America");
}`

Hopefully, if God blesses America thrice, your code is working, I've committed some changes in your code, and all I did was remove the second if statement because usually, we don't need that in recursion (I'm not saying we don't need more than one if statement). Test it yourself and you'll understand why it's so. Hope it helps.

Upvotes: 1

twain249
twain249

Reputation: 5706

You're pretty close

void ft_list_clear(struct Nude *list)
{
   if (!list) { return; }

   ft_list_clear(list->next);
   list->next = null;
   free(list);
}

Explaining the code

The first if checks if the list is currently null and exits the recursion if so.

If the list isn't null recursively call the function. This repeats until the end of the list null. Then since the next has been cleared by the recursive call you can set it to null in this call (not strictly necessary since this clears everything). Finally actually free this node prior to returning to the previous call (this node's parent).

You can also do the delete in the opposite order if you want

void ft_list_clear(string Node *list)
{
   if (!list) { return; }
   struct Node *next = list->next;
   free(list);
   ft_list_clear(next);
}

Same principles just deletes this node before going to the next. This means you don't need to fix the next pointers but you will need to copy them first so you don't lose the reference.

Upvotes: 3

Related Questions