Modify the List<E> class of List.java to include method search that recursively
ID: 3704168 • Letter: M
Question
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
Dear,
Please find my implementation.
// List.java
// ListNode and List class declarations.
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();
}
/**
* method to recursively search for a value and returns it if found. This
* method will call the overloaded search method by passing the firstNode as
* initial argument along with i, which will loop itself until value is
* found or the end of the list is met
*
* @param i
* - value to be searched
* @return - i if found, else null
*/
public E search(E i) {
// creating a reference to first node
ListNode<E> current = firstNode;
// passing the values to recursive search method
return search(i, current);
}
/**
* This is the main method that will recursively call itself until the value
* is found or the end of the list is met
*
* @param i
* - value to be searched
* @param currentNode
* - current node which is being checked
* @return - i if found, else null
*/
public E search(E i, ListNode<E> currentNode) {
if (currentNode != null) {
// current node is not null
if (currentNode.data.equals(i)) {
// found
return i;
} else {
/**
* not equal to the value in current node, searching the next
* node
*/
return search(i, currentNode.getNext());
}
}
//not found
return null;
}
}
//ListTest.java
import java.util.Random;
public class ListTest {
public static void main(String[] args) {
List<Integer> list = new List<Integer>();
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");
}
}
}
//OUTPUT
The list is: 86 90 7 95 66 99 99 80 33 23 7 72 7 96 81 76 74 27 14 54 72 39 92 54 42
Value not found: 34
Value not found: 50
Value found: 72
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.