Modify the List class of List.java to include method search that recursively searches a linked-list object for a specified value. The method should return a reference to the value if its found; otherwise, it should return null. Use your method in a test program that creates a list of integers. The program should prompt the user for a value to locate in the list.

//list.java

// ListNode and List class declarations.

package com.deitel.datastructures;

import java.util.NoSuchElementException;

// class to represent one node in a list

class ListNode {

// package access members; List can access these directly

E data; // data for this node

ListNode nextNode; // reference to the next node in the list

// constructor creates a ListNode that refers to object

ListNode(E object) {this(object, null);}

// constructor creates ListNode that refers to the specified

// object and to the next ListNode

ListNode(E object, ListNode node) {

data = object;

nextNode = node;

}

// return reference to data in node

E getData() {return data;}

// return reference to next node in list

ListNode getNext() {return nextNode;}

}

// class List definition

public class List {

private ListNode firstNode;

private ListNode lastNode;

private String name; // string like "list" used in printing

// constructor creates empty List with "list" as the name

public List() {this("list");}

// constructor creates an empty List with a name

public List(String listName) {

name = listName;

firstNode = lastNode = null;

}

// insert item at front of List

public void insertAtFront(E insertItem) {

if (isEmpty()) { // firstNode and lastNode refer to same object

firstNode = lastNode = new ListNode(insertItem);

}

else { // firstNode refers to new node

firstNode = new ListNode(insertItem, firstNode);

}

}

// insert item at end of List

public void insertAtBack(E insertItem) {

if (isEmpty()) { // firstNode and lastNode refer to same object

firstNode = lastNode = new ListNode(insertItem);

}

else { // lastNode's nextNode refers to new node

lastNode = lastNode.nextNode = new ListNode(insertItem);

}

}

// remove first node from List

public E removeFromFront() throws NoSuchElementException {

if (isEmpty()) { // throw exception if List is empty

throw new NoSuchElementException(name + " is empty");

}

E removedItem = firstNode.data; // retrieve data being removed

// update references firstNode and lastNode

if (firstNode == lastNode) {

firstNode = lastNode = null;

}

else {

firstNode = firstNode.nextNode;

}

return removedItem; // return removed node data

}

// remove last node from List

public E removeFromBack() throws NoSuchElementException {

if (isEmpty()) { // throw exception if List is empty

throw new NoSuchElementException(name + " is empty");

}

E removedItem = lastNode.data; // retrieve data being removed

// update references firstNode and lastNode

if (firstNode == lastNode) {

firstNode = lastNode = null;

}

else { // locate new last node

ListNode current = firstNode;

// loop while current node does not refer to lastNode

while (current.nextNode != lastNode) {

current = current.nextNode;

}

lastNode = current; // current is new lastNode

current.nextNode = null;

}

return removedItem; // return removed node data

}

// determine whether list is empty; returns true if so

public boolean isEmpty() {return firstNode == null;}

// output list contents

public void print() {

if (isEmpty()) {

System.out.printf("Empty %s%n", name);

return;

}

System.out.printf("The %s is: ", name);

ListNode current = firstNode;

// while not at end of list, output current node's data

while (current != null) {

System.out.printf("%s ", current.data);

current = current.nextNode;

}

System.out.println();

}

}