Deleting a Node Using Recursion

[jhykima]

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?

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std; 

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

node *insert (node * head, int x)
{
	node *temp = new node; 
	temp->data = x;
	temp->link = head; 
	head = temp;  
}

node *remove (node *head, int value)
{

	remove (head->next, int value)
}

void print (node *head)
{
	cout << "List is" << " ";  
	node *a = head; 
	while (a != NULL)
	{
		cout << a->data << " "; 
		a = a->link; 
	}
	cout << endl;
}

int main() 
{
	node *head = NULL; 
	int data; 
	int x; 
	int y; 
	cout << "How many numbers" << endl;
	cin >> x;

	for (int i = 0; i < x; i++)
	{	
		cout << "Enter a number" << endl;
		cin >> data; 
		head = insert (head, data);
		print (head); 
	}

	cout << "Which node would you like to remove?" << endl;
	for (int i = 0; i < 10; i++)
	{
		cin >> y; 
		head = remove (head, y); 
		print (head); 
	}
  return 0;
}

[D80DSL3A]

Firstly, the insert function is missing a return value.

node *insert (node * head, int x)// pointer passed by value
{
	node *temp = new node; 
	temp->data = x;
	temp->link = head; 
//	head = temp;  // no point. head is a local copy
        return temp;// this is how head gets updated. Assign to 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:

node *temp = pNode;// save for deletion
pNode = pNode->link;// link across to next node
delete temp;

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.

void remove_node( node*& pNode, int cnt )// pointer passed by reference
{
    // note the 2 terminating conditions
    if( !pNode ) return;// ran off end of list (covers cnt out of range condition)
    if( cnt == 0 )// reached cnt=0 (target node)
    {
        node* temp = pNode;
        pNode = pNode->link;// reason for pass by ref
        delete temp;
        return;// done here
    }

    // Usual case. Not there yet.
    remove_node( pNode->link, cnt-1 );// try the next one. Note decrement in cnt
}

EDIT: Presuming 0 based element counting, like arrays.
eg, for a list with N nodes
remove the 1st node (head) remove_node( head, 0 );
remove the last node (tail) remove_node( head, N-1 );

and code comments

[jhykima]

@fun2code

Thank you so much for your response. I have some questions for you!

Node removal is always the same process regardless of position in list. If pNode points to the node to be removed

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:

node *temp = pNode;// save for deletion
pNode = pNode->link;// link across to next node
delete temp;

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?

for (int i = 0; i < n - 2; i++)
{
	temp1 = temp2->next;
	node *temp2 = temp1->next; 
	temp1->next = temp2->next;
	delete temp2; 
}

Also, why did you write the following?

if( !pNode ) return;

[D80DSL3A]

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

// the value of head is modified in the function
remove_node( head, 0 );

head gets changed because in the function call cnt=0 right away (1st iteration), so pNode==head.
The function is recursive, so in subsequent (recursive) calls

// Usual case. Not there yet.
remove_node( pNode->link, cnt-1 );// passing link by reference 

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.
The traversal is accomplished through the recursive calls.

EDIT: Forgot to answer:

Also, why did you write the following?
if( !pNode ) return;

Perhaps you're more used to seeing if( pNode == NULL )return;// pNode points to nothing . It is the same.

[jhykima]

@fun2code

Thank you so much. I'm currently trying to digest your code. Goodness, you are so helpful. Thank you again!!!

:)

Best regards,
Jae Kim

edit: IT MAKES SO MUCH SENSE. OMY GOODNESS. THANK YOU! And you are a genius.

[jhykima]

@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
pNode->link? So its like, the same code but passing in different values?

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?

[D80DSL3A]

You're welcome. I'm glad my posts made sense.
About treating head vs. some link in the list differently when removing a node:

So its like, the same code but passing in different values?

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?
One difference. In a list with N nodes there are N places to insert after a node, plus one place to insert before - at the head.
Let us keep the add_node(node*, int) function we have for inserting a new head node.
Let's add a new add_node function where the insertion position is given.
Insert after node cnt:
void add_node( node* pNode, int data, int cnt );

Like with node removal, insertion after a node is the same regardless of position in the list.
If pNode points to the node we insert after:

node* temp = new node;
temp->x = data;
temp->link = pNode->link;
pNode->link = temp;

We should be able to adapt the remove function directly.

// remove function
void remove_node( node*& pHead, int cnt )
{
    if( !pHead ) return;
    if( cnt == 0 )
    {
        node* temp = pHead;
        pHead = pHead->link;// reason for pass by ref
        delete temp;
        return;
    }
    remove_node( pHead->link, cnt-1 );// recursion!
}

// insert function
void add_node( node* pNode, int data, int cnt )// passing pointer by value
{
    if( !pNode ) return;
    if( cnt == 0 )
    {
        // the 4 lines from above
        node* temp = new node;
        temp->x = data;
        temp->link = pNode->link;
        pNode->link = temp;// pHead not assigned to directly. No need for pass by ref
        return;
    }
    add_node( pNode->link, data, cnt-1 );// recursion!
}

Now, if I may introduce a simplification method.
It's worth it.
I'll add one function to the node structure. A constructor for automatically initializing the data members x and link.

struct node
{
    int x;
    node* link;
    // constructor
    node( int X=0, node* Link=nullptr): x(X), link(Link) {}// initialization list syntax
};

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:

node* add_node( node* pHead, int X )
{
    node* temp = new node;
    temp->x = X;
    temp->link = pHead;
    return temp;
}

Using the constructor instead of making the individual assignments the function becomes:

node* add_node( node* pHead, int X )
{
    return new node(X, pHead);
}

Applied to the new add_node function:

void add_node( node* pNode, int data, int cnt )// passing pointer by value
{
    if( !pNode ) return;
    if( cnt == 0 )
    {
        pNode->link = new node(data, pNode->link);// all assignments in one shot
        return;
    }
    add_node( pNode->link, data, cnt-1 );// recursion!
}

Here's the add_node function in a different form, which also seems to be working:

void add_node( node* pNode, int data, int cnt )// cnt = 0 to N-1
{
    if( pNode && cnt > 0 )
        add_node( pNode->link, data, cnt-1 );
    else if( pNode )// insert after this node
        pNode->link = new node(data, pNode->link);
}

Let me know if any of these function are working for you! They all work on my end.
I may post back later with fuller code. I have a bunch working.

[jhykima]

@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,
Jae Kim

[jhykima]

@fun2code

The reference makes the identity of the pointer anonymous

Is this statement in regards to the function making a copy of a pointer rather than the pointer itself?

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

void add_node( node* pNode, int data, int cnt )// cnt = 0 to N-1
{
    if( pNode && cnt > 0 )
        add_node( pNode->link, data, cnt-1 );
    else if( pNode )// insert after this node
        pNode->link = new node(data, pNode->link);
}

is after having written the new syntax? node( int X=0, node* Link=nullptr): x(X), link(Link) {}?

Because I tried to run it without the new syntax and several error messages pop up.

[coder777]

I'm sorry but I have never seen this syntax before

This are default parameters/arguments. See:

http://en.cppreference.com/w/cpp/language/default_arguments

Also, I ran the add_node function (the first add_node function) and it won't add a node before the head node.

It doesn't. It inserts the node at a specific index. If you just want to add at the front use your function. This function adds the current node after the indexed node, but you need to do something if there is no head node.

[jhykima]

@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,
Jae Kim

[coder777]

Well, you shouldn't mix before and after. Better name it like so:

void insert_before( node*& pNode, int data, int index, node* prev_node = nullptr )// Note: & and default parameter
{
    if( pNode && index > 0 )
        insert_before( pNode->link, data, index - 1, pNode );
    else
    {
        pNode = new node(data, pNode);
        if(prev_node)
            prev_node->link = pNode;
    }
}

It is actually similar to what fun2code did.

Note that
index-> 0 inserts before head
index-> 1 inserts before the second node (after head)
index-> 2 inserts before the third node (after second node)
etc.

[D80DSL3A]

One function for insertion anywhere? Before or after head?
This follows the same indexing suggested by coder 777 above.

Note that
index-> 0 inserts before head
index-> 1 inserts before the second node (after head)
index-> 2 inserts before the third node (after second node)
etc.

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
int nodeCount(node*);

Here is some complete test code. Note: a destroy list function has also been added:
Also, because the newest insert function insert_node_all can modify the head pointer (when insertion of new head is made) we must pass pNode by reference. Please see comments within function for further reason

#include <iostream>
using std::cout;

struct node
{
    int x;
    node* link;
    node( int X=0, node* Link=nullptr): x(X), link(Link) {}
};

// first version: add node at beginning of list = push_front
node* add_node( node* pHead, int X )
{
    return new node(X, pHead);
}

// 2nd version: insert after existing node
void add_node( node* pNode, int X, int cnt )// cnt = 0 to N-1
{
    if( pNode && cnt > 0 )
        add_node( pNode->link, X, cnt-1 );
    else if( pNode )// insert after this node
        pNode->link = new node(X, pNode->link);// pass by value OK
}

// version 3: insert before or after any node
void add_node_all( node*& pNode, int X, int cnt )// cnt = 0 to N
{
    if( cnt == 0 )// push _front
        pNode = new node(X, pNode);// pass by ref needed for this
    else if( pNode && cnt > 1 )
        add_node_all( pNode->link, X, cnt-1 );
    else if( pNode )// insert after this node
        pNode->link = new node(X, pNode->link);// pass by value OK for this
}

void remove_node( node*& pHead, int cnt )
{
    if( !pHead ) return;
    if( cnt == 0 )
    {
        node* temp = pHead;
        pHead = pHead->link;// reason for pass by ref
        delete temp;
        return;
    }
    remove_node( pHead->link, cnt-1 );// recursion!
}

void display_list( node* pHead )
{
    if( !pHead ){ cout << "empty list\n"; return; }
    while( pHead )
    {
        cout << pHead->x << ' ';
        pHead = pHead->link;
    }
    cout << '\n';
}

void destroy_list( node*& pHead )// passed by ref so pHead = nullptr sticks at the end
{
    int cnt = 0;
    while( pHead )
    {
        node* temp = pHead;
        pHead = pHead->link;
        delete temp;
        ++cnt;
    }
    cout << cnt << " nodes destroyed\n";
}

int nodeCount( node* pNode )// recursive
{
    if( !pNode ) return 0;
    return 1 + nodeCount( pNode->link );
}

int main()
{
    // pointer for a list
    node* pHead = nullptr;// or NULL pre C++11

    // add nodes
    add_node_all( pHead, 10, 1 );// attempt insertion after non-existent head
    display_list( pHead );// empty
    add_node_all( pHead, 10, 0 );// new head
    display_list( pHead );// 10
    add_node_all( pHead, 5, 0 );// new head
    display_list( pHead );// 5 10
    add_node_all( pHead, 8, 1 );// after head
    display_list( pHead );// 5 8 10
    add_node_all( pHead, 15, nodeCount(pHead) );// after tail
    display_list( pHead );// 5 8 10 15
    add_node_all( pHead, 12, 3 );// after 10
    display_list( pHead );// 5 8 10 12 15

    // remove nodes
    remove_node( pHead, 1 );// the 8
    display_list( pHead );// 5 10 12 15
    remove_node( pHead, 3 );// the 15
    display_list( pHead );// 5 10 12
    remove_node( pHead, 0 );// the 5
    display_list( pHead );// 10 12

    // cleanup!
    destroy_list( pHead );// 2 nodes destroyed

    return 0;
}

@coder777
I substituted your insert_before function for insert_node_all in above code and it works the same, except that it will add an initial head node when that 1st line
insert_before( pHead, 10, 1 );// attempt insertion after non-existent head
The function does insert a new head so we get 2 10's in the list.
My function ignores the request, but I'm not sure which behavior is best in that case anyway.

@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.
Any parameter passed by value is useful only for reading from. It cannot be written to. If a value is written it's to the copy produced for use in the function, not to the quantity passed.
Testing if pass by reference is necessary can be done by just removing the & symbol in the parameter list.
If the function still works then pass by reference wasn't necessary.

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.
Removing the & in line 27

 // version 3: insert before or after any node
void add_node_all( node* pNode, int X, int cnt )// cnt = 0 to N. pNode pass by value now 

results in this output

empty list
empty list
empty list
empty list
empty list
empty list
empty list
empty list
empty list
0 nodes destroyed

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:

empty list
10 
5 10 
5 8 10 
5 8 10 15 
5 8 10 12 15 
5 0 10 12 15 
5 0 10 72392256 15 
72392320 0 10 72392256 15 

I think it may have crashed. There's no output from the destroy_list() call.

Desired output, for reference:

empty list
10
5 10
5 8 10
5 8 10 15
5 8 10 12 15
5 10 12 15
5 10 12
10 12
2 nodes destroyed

EDIT: I think coder777 has the function name right. The function does insert before the indexed node.

[jhykima]

@fun2code
@coder777

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!

[jhykima]

@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
How can one compare an integer, the 0, and an address, the pNode? Doesn't the pNode hold the address of the pNode?

I apologize for asking such noobie questions...

[coder777]

This
pNode && index > 0
is short hand for
(pNode != nullptr) && (index > 0)

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).

[jhykima]

@coder777

OOOOHHHH, I see. Thank you for clarifying that for me. And what does index stand for? Sorry for asking so many questions...

[coder777]

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...