Delete a linked list where the delete is after the recursive call c++

Question

For the life of me I can’t figure out how to delete an entire linked list using recursion where the deletion occurs after the recursive call. I tried this:

void remove_nodes(node * &head)
{
     if (!head)
         return;
     remove_nodes(head->next);
     delete head;
}

The node struct is simply:

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

When I use the function above and then display the list, it is still there but with garbage data. I don’t understand what I could be doing wrong.

Probably nothing wrong. The code shown looks good. Don't display after `delete` as the results will be undefined. Sometime you'll get stuff, sometimes you won't. It's almost luck of the draw. — user4581301, Sep 02 '19 at 05:41
Thank you! Yeah apparently my system allows me to access garbage. — Psych, Sep 02 '19 at 05:56
Most systems do allow access to garbage. It can be a significant problem that is justified in the name of speed. A check to ensure that the pointer is valid before accessing it is expensive or impossible and no valid program would do this, so any check would be a performance penalty for correctly written programs. For those programs that are not valid... Well, you're on your own. Fortunately there are tools like asan and valgrind to help you track these suckers down. — user4581301, Sep 02 '19 at 06:08
Ah I see, that makes sense. Thank you! I’ll definitely look into those programs. I’m very new to this, so I greatly appreciate the guidance! — Psych, Sep 02 '19 at 06:29
The best case scenario is the program crashes over invalid memory access because the process no longer owns the memory being read, but as you've seen, you can't count on this. — user4581301, Sep 02 '19 at 06:33
One way to think of it is: When you allocate memory, you take a plot of land and say: "This is my land, nobody else is allowed to build here", and then you can do whatever with that land (f.ex. bulldoze it and build a new house). Then when you free (delete) that memory, you sell the deed and allow others to grab it instead. This does not mean that anybody else _has_ to come and bulldoze your house and build new right away - it just means that they can. As long as nobody else has grabbed that land, your house will still be there - but don't go back, because it _can_ be bulldozed at any time. — Frodyne, Sep 02 '19 at 06:51
[A longer version of Frodyne's comment](https://stackoverflow.com/questions/6441218/can-a-local-variables-memory-be-accessed-outside-its-scope/6445794) — user4581301, Sep 02 '19 at 07:05

score 1 · Accepted Answer · answered Sep 02 '19 at 05:42

1

You never clear the 'next' pointer - you only delete it. Your remove_nodes function probably wants to look like this:

void remove_nodes(node * &head)
{
     if (!head)
         return;
     remove_nodes(head->next);
     delete head;
     head = nullptr;
}

delete head doesn't set head to nullptr; if your display function is checking for a truthy pointer to determine whether to display it's just going to waltz into a deleted object.

answered Sep 02 '19 at 05:42

James Picone

1,509
9
18

Upvoting this because by nulling the pointer this answer solves a future problem: "I want to delete the end of a list and not the whole list." – user4581301 Sep 02 '19 at 05:46
This is perfect! Thank you so much! That’s why I was getting garbage data. I’m entirely new to recursion, so when I should NULL and when it is unnecessary is confusing me. Again, thank you! – Psych Sep 02 '19 at 05:52
1

@Psych Most of the time you don't need to null because you'll never use the variable again. If you suspect you will, you null or rewrite the code so that you never will. In this case you're stuck nulling at least one `head` because you must null terminate the list in order for stuff like `if (!head)` to work. – user4581301 Sep 02 '19 at 06:27

Delete a linked list where the delete is after the recursive call c++

1 Answers1