How to count nodes of a link list by using Recursion in C++

Joe Wilson

12y1.6kVisual Basic .NET

I mean I want to use Recursion function to count nodes of a link list.

3 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes12y ago
Accepted answer
To move through a 'standard' linked list in C++ we need an iterator and we also need to know when the iteration will end because there are no more nodes.

So initially we pass the counter function a pointer to the first node and also a pointer to the position just after the last node.

The total number of nodes is 1 plus the number of nodes from the next position to the end. So we increment the pointer and call the counter function recursively until eventually we get to the end when the stack unwinds and we're left with 0 plus a series of 1's which add up to the number of nodes in the linked list.
+1
Joe Wilson12y ago
Thank you for your answer and could you please explain this part of the project:
I don't understand the codes below.
int counter(list::iterator pos, list::iterator end)
{
if(pos == end) return 0;
return 1 + counter(++pos, end); // recursive call
}
0
Vulpes12y ago
Try this:

#include
#include

using namespace std;

int counter(list::iterator pos, list::iterator end)
{
if(pos == end) return 0;
return 1 + counter(++pos, end); // recursive call
}

int main()
{
list numbers;
list::iterator pos;
int number, count, i;
char lr;

cout << "How many numbers are to be added to the linked list? : ";
cin >> count;
cout << "Enter them" << endl;
for(i = 0; i < count; i++)
{
cout << i + 1 << " : ";
cin >> number;
numbers.push_back(number);
}

cout << endl;

cout << "The numbers entered are" << endl;
for (pos = numbers.begin(); pos != numbers.end(); pos++)
{
cout << *pos << " ";
}

cout << endl << endl;

int size = counter(numbers.begin(), numbers.end());
cout << "There are " << size << " node(s) in the linked list";

return 0;
}
+1