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

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();