Modify the List<E> class of List.java to include method search that recursively
ID: 3706787 • 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 the test program
provided below to create a list of integers.
************************************************
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();
}
}
***********************************************
Use the class ListTest.java to test your code.
ListTest.java
// 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
Hello, I have already answered a similar question before, so I’m referring it here. I have modified your code to include a recursive searching functionality to search for a value. Also, defined an overloaded version of search method() to carry out the main recursive iteration through the list elements and search for the data. Comments are included, go through it and let me know if you have any doubts. Thanks.
// 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.