Please do not copy an answer from another chegg expert. Modify the List<E> class
ID: 3707974 • Letter: P
Question
Please do not copy an answer from another chegg expert.
Modify the List<E> 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 it’s 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<E> {
// package access members; List can access these directly
E data; // data for this node
ListNode<E> 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<E> node) {
data = object;
nextNode = node;
}
// return reference to data in node
E getData() {return data;}
// return reference to next node in list
ListNode<E> getNext() {return nextNode;}
}
// class List definition
public class List<E> {
private ListNode<E> firstNode;
private ListNode<E> 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<E>(insertItem);
}
else { // firstNode refers to new node
firstNode = new ListNode<E>(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<E>(insertItem);
}
else { // lastNode's nextNode refers to new node
lastNode = lastNode.nextNode = new ListNode<E>(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<E> 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<E> 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<Integer> 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");
}
}
}
Explanation / Answer
Below is your code... All changes are in bold: -
List.java
// ListNode and List class declarations.
package com.deitel.datastructures;
// class to represent one node in a list
class ListNode<E> {
// package access members; List can access these directly
E data; // data for this node
ListNode<E> 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<E> node) {
data = object;
nextNode = node;
}
// return reference to data in node
E getData() {
return data;
}
// return reference to next node in list
ListNode<E> getNext() {
return nextNode;
}
}
// class List definition
public class List<E> {
private ListNode<E> firstNode;
private ListNode<E> 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<E>(insertItem);
} else { // firstNode refers to new node
firstNode = new ListNode<E>(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<E>(insertItem);
} else { // lastNode's nextNode refers to new node
lastNode = lastNode.nextNode = new ListNode<E>(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<E> 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<E> 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();
}
public E search(E i) {
//if list is empty return null
if (isEmpty()) {
return null;
}
ListNode<E> current = firstNode;
//loop through list and check if element is found return it
while (current != null) {
if (current.data.equals(i)) {
return current.data;
}
current = current.nextNode;
}
//if not found return null
return null;
}
}
ListTest.java
public class ListTest {
public static void main(String[] args) {
List<Integer> 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");
}
Scanner sc = new Scanner(System.in);
System.out.print("Please enter a value to search : ");
int numToSearch = sc.nextInt();
searchResult = list.search(numToSearch);
// display result of searching user input data
if (searchResult != null) {
System.out.println("Value found: "+searchResult);
} else {
System.out.println("Value not found: "+numToSearch);
}
}
}
Output
The list is: 60 46 95 45 28 20 78 43 51 4 88 82 42 39 75 33 58 59 22 73 10 74 33 56 57
Value not found: 34
Value not found: 50
Value not found: 72
Please enter a value to search : 46
Value found: 46
2nd run
The list is: 8 15 3 32 41 37 83 66 29 93 92 16 29 13 72 56 95 2 86 70 85 57 7 69 68
Value not found: 34
Value not found: 50
Value found: 72
Please enter a value to search : 9
Value not found: 9