Top List List

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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

@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:

1
2
3

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?

1
2
3
4
5
6
7

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?

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

1 2	// 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

1 2	// 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.

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

@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?

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:

1
2
3
4

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

We should be able to adapt the remove function directly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

1
2
3
4
5
6
7

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:

1
2
3
4
5
6
7

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:

1
2
3
4

node* add_node[ node* pHead, int X ] { return new node[X, pHead]; }

Applied to the new add_node function:

1
2
3
4
5
6
7
8
9
10

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:

1
2
3
4
5
6
7

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.

@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

@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

1
2
3
4
5
6
7

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.

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

This are default parameters/arguments. See:

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

@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

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

1
2
3
4
5
6
7
8
9
10
11

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.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

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

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

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

Video liên quan

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề