The mode of a list of values is the value having the greatest frequency. In your pre-lab you wrote an algorithm to find the mode of the sorted list. Your task is to implement this method in three ways:

b. Assuming a linked implementation manipulate the linked list directly - implement method getMode in SortedLinkedListWithMode.java.

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 <= this.numberOfEntries)) { assert !isEmpty(); result = getNodeAt(givenPosition).data; } // end if return result; } // end getEntry public T remove(int givenPosition) { T result = null; // Return value if ((givenPosition >= 1) && (givenPosition <= this.numberOfEntries)) { assert !isEmpty(); if (givenPosition == 1) // Case 1: remove first entry { result = this.firstNode.data; // Save entry to be removed this.firstNode = this.firstNode.next; } else // Case 2: 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 < this.numberOfEntries) && (currentNode != null)) { result[index] = currentNode.data; currentNode = currentNode.next; index++; } // end while return result; } // end toArray public void display() { System.out.print(" The data has " + this.numberOfEntries + " element(s): "); Node currentNode = this.firstNode; int index = 0; while ((index < this.numberOfEntries) && (currentNode != null)) { System.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 <= givenPosition) && (givenPosition <= this.numberOfEntries); Node currentNode = this.firstNode; // Traverse the list to locate the desired node for (int counter = 1; counter < givenPosition; counter++) currentNode = currentNode.next; assert currentNode != null; return currentNode; } // end getNodeAt private class Node  { 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 < 10; i++) data.add(i); data.display(); System.out.println("The mode should be 0, got: " + data.getMode()); for (int i = 0; i < 10; i++) for (int j = 0; j < i; j++) data.add(i); data.display(); System.out.println("The mode should be 9, got: " + data.getMode()); for (int i = 0; i < 21; i++) for (int j = 8; j < i; j++) data.add(i); data.display(); System.out.println("The mode should be 20, got: " + data.getMode()); for (int i = 0; i < 14; i++) data.add(6); data.display(); System.out.println("The mode should be 6, got: " + data.getMode()); System.out.println(" *** Done ***"); } // end main } // end LinkedSortedList 

See 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 ***