Delete node in linked list using recursion
I have been struggling with this problem for about 4 hours. And this is not a school assignment or anything. Can anyone help me have a logical understanding of how to code this? Also, I do not want to delete the node by value. I want to delete the node by placement. For example, delete the third node or the second node. The main problem rises when I try to take in to account deleting the first node. I think I can delete the nth node using recursion. But not the nth node AND the 1st node in a single recursive function. Any suggestions?
Firstly, the insert function is missing a return value.
That should work better. Node removal is always the same process regardless of position in list. If pNode points to the node to be removed, then:
The key is passing the pointer by reference, so the assignment on line 2 above is made to the actual pointer passed to the function (and not some local copy). The recursive function below works by decrementing cnt for the next call. When cnt == 0 the node has been reached.
EDIT: Presuming 0 based element counting, like arrays. and code comments @fun2code Thank you so much for your response. I have some questions for you!
Isn't there is a difference between removing the head node and a none head node? To delete the head node you write, what you wrote:
To delete the node that is not a head node, wouldn't you have to traverse to the node before the node that you want to remove? And connect that node to the node that is after the node that you delete? Something like this?
Also, why did you write the following? Removal of the head node works the same way as any other, except that you're working with a pointer to head. To remove the head (1st node) call
head gets changed because in the function call cnt=0 right away (1st iteration), so pNode==head.
the pointer passed is pNode->link, which is the one needing modification for a mid-list removal. Hope that makes sense. Some of the reasoning is subtle. Try drawing some diagrams. There is no for loop because the function is recursive, as requested in the thread topic. EDIT: Forgot to answer:
Perhaps you're more used to seeing if( pNode == NULL )return;// pNode points to nothing. It is the same. @fun2code Thank you so much. I'm currently trying to digest your code. Goodness, you are so helpful. Thank you again!!! :) Best regards, edit: IT MAKES SO MUCH SENSE. OMY GOODNESS. THANK YOU! And you are a genius. @fun2code Now, looking at your code, it seems to me that, technically, there is a difference between deleting the head node and the nodes in the list correct? Because for deleting the head node, the code passes in the pointer to the head node, whereas, the other times, passes in the So I have been trying to use similar logic to try to add a node as well. I've been trying to write code that would add a node before the first node and among the other nodes. And I have yet to be successful. Any hints? You're welcome. I'm glad my posts made sense. About treating head vs. some link in the list differently when removing a node:
Yes. The reference makes the identity of the pointer anonymous. In the 1st iteration pNode refers to head. In subsequent iterations pNode refers to some link in the list. About an insert_node function where the insertion position is given, like the remove node function above? Like with node removal, insertion after a node is the same regardless of position in the list.
We should be able to adapt the remove function directly.
Now, if I may introduce a simplification method.
The overloaded values for x (0) and link (nullptr) are given so it's still possible to declare a node like so: node N; But we'll find it useful to use node N(data, pNext); Consider our add_node function:
Using the constructor instead of making the individual assignments the function becomes:
Applied to the new add_node function:
Here's the add_node function in a different form, which also seems to be working:
Let me know if any of these function are working for you! They all work on my end. @fun2code Awesome. Thank you so much for your response again. Like seriously, I appreciate your taking the time to help me out sooo much!!! I am currently digesting your code. Best regards, @fun2code
Why did you, for the remove function pass by reference and for add_node function, you chose not to? Also, isn't it possible to write the remove function without passing by reference? Also, I ran the add_node function (the first add_node function) and it won't add a node before the head node. Anyway to write the function differently to account for this? I'm sorry but I have never seen this syntax before node( int X=0, node* Link=nullptr): x(X), link(Link) {} Perhaps, I should learn what this means before I am able to understand the rest of your code? Any resources that you can point me to? Also, I am assuming this
Because I tried to run it without the new syntax and several error messages pop up.
http://en.cppreference.com/w/cpp/language/default_arguments
@coder777 Thank you for the resource. I'll take a look at that. I see. Is there a way to write a single recursive function that can add a node before the head as well as adding a node after the indexed node? Best regards, Well, you shouldn't mix before and after. Better name it like so:
Note that One function for insertion anywhere? Before or after head? This follows the same indexing suggested by coder 777 above.
For insertion after the tail: index-> N insert after tail in list with N nodes. To help with getting the number of nodes correct, I'll include a helper function Here is some complete test code. Note: a destroy list function has also been added:
@coder777 @jhykima. The matter of passing pointers by value vs. by reference depends on whether the pointer will be reassigned a value directly or not. This rule applies regardless of the variable type. If you want a function to modify an int parameter it must be passed by reference. EDIT: A quick experiment using the shell runner here Click the wheel at the top right corner of the code, modify code as desired then click run.
results in this output
This is because no head was added (pHead stays = nullptr) since the function can't assign a new value to pNode. Removal of the & in remove_node results in this mess:
I think it may have crashed. There's no output from the destroy_list() call. Desired output, for reference:
EDIT: I think coder777 has the function name right. The function does insert before the indexed node. @fun2code I apologize for not making my question clearer regarding adding the node before or after. I'll be careful to be more specific in my questions next time. Thank you so much for answering my questions and more! I''ll try to digest what you guys have so generously written. Thank you! @coder777 I am currently looking at the code and what does index stand for and what does it do? Also, I'm confused as to how the following code is possible: pNode && index > 0 I apologize for asking such noobie questions... This if clauses know just true and false. An expression that results 0 is false while everything not 0 is true. A nullptr is also considered 0. pNode contains the address of the node you're passing to the function (it can be nullptr). @coder777 OOOOHHHH, I see. Thank you for clarifying that for me. And what does index stand for? Sorry for asking so many questions... The index is the position where the node is inserted. Like an index of an array. In this recursive case the index is relative to the passed node. The use of this index is questionable... Topic archived. No new replies allowed. |