Modify the List class of Fig. 21.3 to include method search that recursively searches a linked-list object
Question:
Modify the List class of Fig. 21.3 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.
Fig. 21.3
Transcribed Image Text:
I // Fig. 21.3: List.java 2 // ListNode and List class declarations. 3 package com.deitel.datastructures; 4 5 6 7 8 9 10 II 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 32 33 34 35 36 37 38 39 40 41 42 43 44 27 28 } 29 30 // class List definition 31 public class List { 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 import java.util. NoSuch ElementException; // 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 126 127 // constructor creates a ListNode that refers to object ListNode(E object) {this (object, null); } 128 129 // 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;} 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 } // 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); } listName; firstNode = lastNode= null; } } 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); 130 131 } 132 } } // remove first node from List public E removeFromFront () throws NoSuchElementException { if (isEmpty()) { // throw exception if List is empty throw new NoSuch ElementException (name + " is empty"); } E removedItem = firstNode.data; // retrieve data being removed // update references firstNode and lastNode if (firstNode = lastNode) { firstNode = lastNode = null; } else { } 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 NoSuch ElementException (name + " is empty"); } E removedItem = lastNode.data; // retrieve data being removed // update references firstNode and lastNode if (firstNode == lastNode) { firstNode firstNode.nextNode; } } else { // locate new last node ListNode current = firstNode; firstNode = lastNode = null; 106 107 108 109 } 110 [[| // determine whether list is empty; returns true if so public boolean isEmpty() {return firstNode == null; } 112 113 114] 115 116 117 118 119 120 121 122 123 124 124 125 } // 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 // 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();
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 50% (2 reviews)
To fulfill the questions requirement we need to add a search method to the List class that employs r...View the full answer
Answered By
Branice Buyengo Ajevi
I have been teaching for the last 5 years which has strengthened my interaction with students of different level.
4.30+
1+ Reviews
10+ Question Solved
Related Book For
Java How To Program Late Objects Version
ISBN: 9780136123712
8th Edition
Authors: Paul Deitel, Deitel & Associates
Question Posted:
Students also viewed these Computer science questions
-
Modify the List class of Fig. 21.3 to include method printListBackward that recursively outputs the items in a linked-list object in reverse order. Write a test program that creates a list of...
-
Modify the SortedList class from Exercise 21.7 to include a merge method that can merge the SortedList it receives as an argument with the SortedList that calls the method. Write an application to...
-
As presented in the text, linked lists must be searched sequentially. For large lists, this can result in poor performance. A common technique for improving list-searching performance is to create...
-
In Problems 1130, solve each equation by factoring. x 2 - 9x = 0
-
(a) For an excited state of hydrogen, show that the smallest angle that the orbital angular momentum vector L can have with the z-axis is(b) What is the corresponding expression for (?L)max the...
-
You wish to boil 1.1 kg of water, which has a specific heat capacity of 4186 J/kg-K. The water is initially at room temperature (293 K). Water boils at 373 K. 1) How much energy must be added to the...
-
The equation of motion of a simple pendulum subject to viscous damping can be expressed as \[\ddot{\theta}+c \dot{\theta}+\sin \theta=0\] If the initial conditions are \(\theta(0)=\theta_{0}\) and...
-
The controller for Clint Eastwood Co. is attempting to determine the amount of cash to be reported on its December 31, 2008, balance sheet. The following information is provided. 1. Commercial...
-
Allegedly, IKEA has been planning to open its flagship store in India for years now (I remember getting wind of it as long as 5 years ago). Now that the store is finally up and running, there's one...
-
In this exercise, we discuss deleting items from binary search trees. The deletion algorithm is not as straightforward as the insertion algorithm. Three cases are encountered when deleting an itemthe...
-
Modify Figs. 21.15 and 21.16 so the Tree class provides a method getDepth that determines how many levels are in the tree. Test the method in an application that inserts 20 random integers into a...
-
What is the WTO and what is its role in world trade?
-
Instructions: Imagine that you are landscaper who is designing a backyard for your clients. The backyard must contain a pond, flower bed with a sprinkler system, a pool with a concrete border, and a...
-
n JART manufactures and sells underwater markers. Its contribution margin income statement follows Contribution Margin Income Statement Per Unit $ 6.00 For Year Ended December 31 Sales (410, 0e0...
-
For each bond from A to F, complete the following table based on the information provided and determine: a. The payments generated b. The current yield Current/market Bond A B C D E F value $1,200...
-
Calculate the cash flow of this project? After -tax Salvage Value Tax at 40.00% Add: Depreciation Total Overhead Cost (S) $ Before Tax Cash Flows (S) ($) $ After Tax Cash Flows ($) (S) N/A S S S S...
-
The attached Excel file contains financial statements-income statements and balance sheets - for two companies operating major airlines - United Airlines Holdings, Inc. (ticker: UAL) and Spirit...
-
1. Why is the metric system preferred worldwide to the U.S. system of measurement? 2. List a very large and a very small measurement that could be usefully written in scientific notation. 3. When...
-
Find the image of x = k = const under w = 1/z. Use formulas similar to those in Example 1. y| y = 0 -21 -2 -1 -1, /1 12 T -1 -1 y= -2 x =0
-
What is the maximum number of callers in each cell in AMPS?
-
What are the functions of a mobile switching center?
-
What is the maximum number of simultaneous calls in each cell in an IS-136 (D-AMPS) system, assuming no analog control channels?
-
Sales, Production, Direct Materials Purchases, and Direct Labor Cost Budgets The budget director of Gourmet Grill Company requests estimates of sales, production, and other operating data from the...
-
Sam, married filing separately without dependents, has $ 3 2 5 , 0 0 0 salary and $ 7 5 , 0 0 0 qualified dividends. Her taxable income is $ 3 8 0 , 0 0 0 . Compute Sam's total tax liability for the...
-
The following is a list of account titles and amounts ( in thousands ) as reported at June 3 0 , 2 0 2 0 , by Darian s Dirt Bikes, Inc., a retail distributor of motorcycles: Buildings and...
Study smarter with the SolutionInn App