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 test method merge.

Exercise 21.7

Write a program that inserts 25 random integers from 0 to 100 in order into a linked-list object. For this exercise, you’ll need to modify the List class (Fig. 21.3) to maintain an ordered list. Name the new version of the class SortedList.

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 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 } 29 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 30 // class List definition 31 public class List { 32 33 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 106 107 108 109 110 112 113 114] 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 115 116 117 118 119 120 121 122 123 124 124 125 126 127 128 129 // 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 node) { object; data 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 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 (insertItem); } } } 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); } // remove first node from List public E removeFrom Front () throws No SuchElement Exception { 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; 130 131 } 132 } } 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 removed Item = 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; } // loop while current node does not refer to lastNode while (current.nextNode != lastNode) { current = current.nextNode; } } return removedItem; // return removed node data. } // determine whether list is empty; returns true if so public boolean isEmpty() {return firstNode == null; } lastNode = current; // current is new lastNode current.nextNode = 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 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.printIn();