(Recursively Search a List) Write a member function searchList that recursively searches a linked list object for a specified value. The function should return a pointer to the value if it is found; otherwise, null should be returned. Use your function in a test program that creates a list of integers. The program should prompt the user for a value to locate in the list.

Question

What will be an ideal response?

Answer 1

```
// ListNode class template definition.
#ifndef LISTNODE_H
#define LISTNODE_H

template< typename T > class List; // forward declaration

template< typename NODETYPE >
class ListNode
{
friend class List< NODETYPE >; // make List a friend
public:
ListNode( const NODETYPE & ); // constructor
NODETYPE getData() const; // return the data in the node

// set the next pointer
void setNextPtr( ListNode *nPtr )
{
nextPtr = nPtr;
} // end function setNextPtr

// get the next pointer
ListNode *getNextPtr() const
{
return nextPtr;
} // end function getNextPtr

// get the address
NODETYPE *getAddress()
{
return &data;
} // end function getAddress
private:
NODETYPE data; // data
ListNode *nextPtr; // next node in the list
}; // end class ListNode

// constructor
template< typename NODETYPE >
ListNode< NODETYPE >::ListNode( const NODETYPE &info )
{
data = info;
nextPtr = 0;
} // end ListNode constructor

// return a copy of the data in the node
template< typename NODETYPE >
NODETYPE ListNode< NODETYPE >::getData() const
{
return data;
} // end getData

#endif
```
```
// List2 class template definition
#ifndef LIST2_H
#define LIST2_H

#include
#include
#include "ListNode.h"
#include "List.h"
using namespace std;

template< typename NODETYPE >
class List2 : public List< NODETYPE >
{
public:
NODETYPE *searchList( NODETYPE & ) const;
private:
// utility function
NODETYPE *recursiveSearchHelper(
ListNode< NODETYPE > *, NODETYPE & ) const;
}; // end class List2

// Search a List recursively.
template< typename NODETYPE >
NODETYPE *List2< NODETYPE >::searchList( NODETYPE &val ) const
{
return recursiveSearchHelper( firstPtr, val );
} // end function recursiveSearch

// Helper for searching a list recursively.
template< typename NODETYPE >
NODETYPE *List2< NODETYPE >::recursiveSearchHelper(
ListNode< NODETYPE > *currentPtr, NODETYPE &value ) const
{
if ( currentPtr == 0 )
return 0;

// if data is found
if ( currentPtr->getData() == value )
return currentPtr->getAddress();

// continue recursive call
return recursiveSearchHelper( currentPtr->getNextPtr(), value );
} // end function recursiveSearchHelper

#endif
```
```
#include
using namespace std;

#include "List2.h"

int main()
{
List2< int > intList;

// create list
for ( int i = 2; i <= 20; i += 2 )
intList.insertAtBack( i );

intList.print(); // print list

int value;
int *ptr; // int pointer

cout << "Enter a value to search for: ";
cin >> value;
ptr = intList.searchList( value );

if ( ptr != 0 )
cout << *ptr << " was found\n";
else
cout << "Element not found\n";

return 0; // indicates successful termination
} // end main
```
The list is: 2 4 6 8 10 12 14 16 18 20
Enter a value to search for: 18
18 was found
Destroying nodes ...
2 4 6 8 10 12 14 16 18 20
All nodes destroyed