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...
-
There is an advantage in performing one ____- way ANOVA over two ____-way ANOVAs.
-
Identify which of the following numbers are irrational: \(\frac{13}{\sqrt{46}}, 4+13 \pi, \sqrt{144}, \frac{5}{9}\)
-
1. Describe the situation at Lehman Brothers from an ethics perspective. Whats your opinion of what happened here? 2. What was the culture at Lehman Brothers like? How did this culture contribute to...
-
Problem 1 (5 pts). - Follow the format of the entity definitions on P.57 of the text, define the entity given below according to your last name; identify two distinguishing attributes of the entity:...
-
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...
-
Use the direct gradient descent algorithm (9.120) using the value of d k found in Exercise 9.6.14 to solve the linear systems in Exercise 9.6.7. Compare the speed of convergence with that of the...
-
9. Construction sand is piled in a right cone that has a height of 30 feet and a diameter of 110 feet. The sand has a density of 98.0 lb/ft. a) Determine the volume of the cone to the nearest 0.1 ft....
-
How was Pepsi able to come back from near bankruptcy and gain share at the expense of Coke from the 19505 through to 1975?
-
How can a product manager learn market research, design thinking, business planning and go-to-market strategy?
-
A worker is paid differential piecework. The scheme is as follows: Units per day Up to 50 51-70 Units per day 71-80 Units per day 81 - 100 Units per day N50 per unit N60 per unit N65 per unit N70 per...
-
How might an individual artificially acquire passive immunity to influenza?
-
1. Who are the stakeholders involved, and what are their interests? 2. Which stakeholders and interests are the most important? Why? 3. What was wrong with the quality of the board of directors...
-
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?
-
Question 13 A regression is calculated on a data set of coordinate pairs (x, y). The resulting regression model is f(x) = A + Bln x, where A > 0 and B > 1. The same model can be expressed as g(x) =...
-
Question 3 (1.5 points) Use Identities to find the exact value. cos 255 1) 2-6 4 2) 2 - 6 3)2 - 4) 6-2 4
-
Question 4 Not yet answered Marked out of 1.00 In the following figure, D = 92 cm and r = 15 mm. The inductance of each conductor is equal to: O a. 1.22 mH/km O b. 0.41 mH/km O c. 0.36 mH/km O d....
Study smarter with the SolutionInn App