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(); } }

=========ListTest.java to test the code==========

// Exercise 21.21 Solution: ListTest.java // Program recursively searches a list of numbers. import java.util.Random;

public class ListTest { public static void main(String[] args) { List list = new List<>(); int number; Random randomNumber = new Random();

// create objects to store in the List for (int i = 0; i <25; i++) { number = randomNumber.nextInt(101); list.insertAtFront(number); }

list.print(); Integer searchResult = list.search(34);

// display result of searching 34 if (searchResult != null) { System.out.println("Value found: 34"); } else { System.out.println("Value not found: 34"); } searchResult = list.search(50);

// display result of searching 50 if (searchResult != null) { System.out.println("Value found: 50"); } else { System.out.println("Value not found: 50"); } searchResult = list.search(72);

// display result of searching 72 if (searchResult != null) { System.out.println("Value found: 72"); } else { System.out.println("Value not found: 72"); } } }

/************************************************************************** * (C) Copyright 1992-2018 by Deitel & Associates, Inc. and * * Prentice Hall. All Rights Reserved. * * * * DISCLAIMER: The authors and publisher of this book have used their * * best efforts in preparing the book. These efforts include the * * development, research, and testing of the theories and programs * * to determine their effectiveness. The authors and publisher make * * no warranty of any kind, expressed or implied, with regard to these * * programs or to the documentation contained in these books. The authors * * and publisher shall not be liable in any event for incidental or * * consequential damages in connection with, or arising out of, the * * furnishing, performance, or use of these programs. * *************************************************************************/