Question

Write a C++ recursive function that counts the number of nodes in a singly linked list.

(a) Test your function using different singly linked lists. Include your code.

(b) Write a recurrence relation that represents your algorithm.

(c) Solve the recurrence relation using the iterating or recursive tree method to obtain the running time of the algorithm in Big-O notation.

Answer 1

#include<iostream>

#include<cstdlib>

using namespace std;

struct Node

{

int data;

struct Node *next;

};

// This function prints contents of linked list starting from

// the given node

void printList(Node *n)

{

while (n != NULL)

{

cout<< n->data<<" ";

n = n->next;

}

cout<<endl;

}

// function to count the size

int size(Node *head) {

if(head == NULL)

return 0;

return 1 + size(head->next); // recursive call

}

int main()

{

Node* head = NULL;

Node* second = NULL;

Node* third = NULL;

// allocate 3 nodes in the heap

head = new Node;

second = new Node;

third = new Node;

head->data = 1; //assign data in first node

head->next = second; // Link first node with second

second->data = 2; //assign data to second node

second->next = third;

third->data = 3; //assign data to third node

third->next = NULL;

printList(head);

cout<<"Size of list: "<<size(head)<<endl;

return 0;

}

b)

T(n) = 1 + T(n-1)

c)

T(n) = 1 + T(n-1)

= 1 + 1 + T(n-2)

= 1 + 1+ 1+... n times

= O(n)