Implemement this program in Java. The instructions, skeleton program, and sample run are given below.

----------------

SortedLinkedListWithMode.java

package Lab10; /**  * A class that implements the ADT sorted list by using a chain of linked nodes.  * Duplicate entries are allowed.  *  * @author YOUR NAME  * @version 10/30/2018  */ public class SortedLinkedListWithMode> implements SortedListInterface { private Node firstNode; // Reference to first node of chain private int numberOfEntries; public SortedLinkedListWithMode() { this.firstNode = null; this.numberOfEntries = 0; } // end default constructor // Part b: manipulating directly the instance variables of SortedLinkedListWithMode, // find the mode. The mode is the most frequent value. // vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv public T getMode() { // TODO Project 2b  T mode = null; int modeCount = 0; System.out.println("IMPLEMENT Part b: manipulating directly the instance variables of SortedLinkedListWithMode," + "find the mode. The mode is the most frequent value."); System.out.println("---> mode is " + mode + "; mode count is " + modeCount ); return mode; } // end getMode // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ public void add(T newEntry) { Node newNode = new Node(newEntry); Node nodeBefore = getNodeBefore(newEntry); if (isEmpty() || (nodeBefore == null)) { // Add at beginning newNode.next = this.firstNode; this.firstNode = newNode; } else { // Add after nodeBefore Node nodeAfter = nodeBefore.next; newNode.next = nodeAfter; nodeBefore.next = newNode; } // end if this.numberOfEntries++; } // end add public boolean remove(T anEntry) { boolean found = false; if (this.numberOfEntries > 0) { Node nodeToRemove; Node nodeBefore = getNodeBefore(anEntry); if (nodeBefore == null) nodeToRemove = this.firstNode; else nodeToRemove = nodeBefore.next; if ((nodeToRemove != null) && anEntry.equals(nodeToRemove.data) ) { found = true; if (nodeBefore == null) this.firstNode = nodeToRemove.next; else { Node nodeAfter = nodeToRemove.next; nodeBefore.next = nodeAfter; } // end if this.numberOfEntries--; } // end if } // end if return found; } // end remove public int getPosition(T anEntry) { int position = 1; Node currentNode = this.firstNode; while ( (currentNode != null) && ( anEntry.compareTo(currentNode.data) > 0) ) { currentNode = currentNode.next; position++; } // end while if ( (currentNode == null) || anEntry.compareTo(currentNode.data) != 0) position = -position; return position; } // end getPosition // List operations public T getEntry(int givenPosition) { T result = null; // Result to return if ((givenPosition >= 1) && (givenPosition = 1) && (givenPosition  1 { Node nodeBefore = getNodeAt(givenPosition - 1); Node nodeToRemove = nodeBefore.next; Node nodeAfter = nodeToRemove.next; nodeBefore.next = nodeAfter; // Disconnect the node to be removed result = nodeToRemove.data; // Save entry to be removed } // end if this.numberOfEntries--; } // end if return result; // Return removed entry, or // null if operation fails } // end remove public final void clear() { this.firstNode = null; this.numberOfEntries = 0; } // end clear public boolean contains(T anEntry) { return getPosition(anEntry) > 0; } // end contains public int getLength() { return this.numberOfEntries; } // end getLength public boolean isEmpty() { boolean result; if (this.numberOfEntries == 0) // Or getLength() == 0 { assert this.firstNode == null; result = true; } else { assert this.firstNode != null; result = false; } // end if return result; } // end isEmpty public T[] toArray() { // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") T[] result = (T[])new Comparable[this.numberOfEntries]; // Warning: unchecked cast int index = 0; Node currentNode = this.firstNode; while ((index out.print(" The data has " + this.numberOfEntries + " element(s): "); Node currentNode = this.firstNode; int index = 0; while ((index out.print(currentNode.data + " "); currentNode = currentNode.next; } System.out.println(); } // Finds the node that is before the node that should or does // contain a given entry. // Returns either a reference to the node that is before the node // that does or should contain anEntry, or null if no prior node exists // (that is, if anEntry belongs at the beginning of the list). private Node getNodeBefore(T anEntry) { Node currentNode = this.firstNode; Node nodeBefore = null; while ( (currentNode != null) && (anEntry.compareTo(currentNode.data) > 0) ) { nodeBefore = currentNode; currentNode = currentNode.next; } // end while return nodeBefore; } // end getNodeBefore private Node getNodeAt(int givenPosition) { assert !isEmpty() && (1  currentNode = this.firstNode; // Traverse the list to locate the desired node for (int counter = 1; counter  { private S data; // Entry in list private Node next; // Link to next node private Node(S dataPortion) { this.data = dataPortion; this.next = null; } // end constructor private Node(S dataPortion, Node nextNode) { this.data = dataPortion; this.next = nextNode; } // end constructor } // end Node public static void main(String args[]) { SortedLinkedListWithMode data = new SortedLinkedListWithMode(); System.out.println("The mode of the empty list should be null, got: " + data.getMode()); // test list of 1 element data.add(9); data.display(); System.out.println("The mode should be 9, got: " + data.getMode()); // test list of 2 elements data.add(13); data.display(); System.out.println("The mode should be 9, got: " + data.getMode()); // test list of 3 elements data.add(13); data.display(); System.out.println("The mode should be 13, got: " + data.getMode()); // test list of 3 elements data = new SortedLinkedListWithMode(); data.add(9); data.add(9); data.add(13); data.display(); System.out.println("The mode should be 9, got: " + data.getMode()); data = new SortedLinkedListWithMode(); for (int i = 0; i out.println("The mode should be 0, got: " + data.getMode()); for (int i = 0; i out.println("The mode should be 9, got: " + data.getMode()); for (int i = 0; i out.println("The mode should be 20, got: " + data.getMode()); for (int i = 0; i out.println("The mode should be 6, got: " + data.getMode()); System.out.println(" *** Done ***"); } // end main } // end LinkedSortedList 

---------

SortedListInterface.java

package Lab10; public interface SortedListInterface> { /** Adds a new entry to this sorted list in its proper order.  The list's size is increased by 1.  @param newEntry The object to be added as a new entry. */  public void add(T newEntry); /** Removes the first or only occurrence of a specified entry  from this sorted list.  @param anEntry The object to be removed.  @return True if anEntry was located and removed;  otherwise returns false. */  public boolean remove(T anEntry); /** Gets the position of an entry in this sorted list.  @param anEntry The object to be found.  @return The position of the first or only occurrence of anEntry  if it occurs in the list; otherwise returns the position  where anEntry would occur in the list, but as a negative  integer. */  public int getPosition(T anEntry); // The following methods are described in Segment 12.9 of Chapter 12 // as part of the ADT list: public T getEntry(int givenPosition); public boolean contains(T anEntry); public T remove(int givenPosition); public void clear(); public int getLength(); public boolean isEmpty(); public T[] toArray(); } // end SortedListInterface 

-------------

Sample Run:

---> mode is null; mode count is 0

The mode of the empty list should be null, got: null

The data has 1 element(s): 9

---> mode is 9; mode count is 1

The mode should be 9, got: 9

The data has 2 elements: 9 13

---> mode is 9; mode count is 1

The mode should be 9, got: 9

The data has 3 elements: 9 13 13

---> mode is 13; mode count is 2

The mode should be 13, got: 13

The data has 3 elements: 9 9 13

---> mode is 9; mode count is 2

The mode should be 9, got: 9

The data has 10 elements: 0 1 2 3 4 5 6 7 8 9

---> mode is 0; mode count is 1

The mode should be 0, got: 0

The data has 55 elements: 0 1 1 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9

---> mode is 9; mode count is 10

The mode should be 9, got: 9

The data has 133 elements: 0 1 1 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 10 10 11 11 11 12 12 12 12 13 13 13 13 13 14 14 14 14 14 14 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 20

---> mode is 20; mode count is 12

The mode should be 20, got: 20

The data has 147 elements: 0 1 1 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 10 10 11 11 11 12 12 12 12 13 13 13 13 13 14 14 14 14 14 14 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 20

---> mode is 6; mode count is 21

The mode should be 6, got: 6

*** Done ***

II. The mode of a list of values is the value having the greatest frequency. Find the mode of the sorted list. Your task is to implement this method in this way b. Assuming a linked implementation manipulate the linked list directly - implement method getMode in SortedLinkedListWithMode.java