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. package com.deitel.datastructures; 3 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 27 28 } 29 30 // class List definition 31 public class List { 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.NoSuchElementException; // 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) { } // 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); } name 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();