Question

The mode of a list of values is the value having the greatest frequency. ( You will implement this algorithm in the lab - project 3)

write an algorithm in pseudocode to find the mode of a sorted list in one pass using only iterator

Lab10-Project3 Description

FindMode

You are working with a sorted list of numbers that are stored in SortedLinkedListWithIterator object called this.myList. Duplicates are allowed. Your task is to find a mode of the list - the value having the greatest frequency. Your algorithm needs to accomplish this task in one pass utilizing the iterator.

Answer 1

public class SortedLinkedListWithMode<T extends Comparable<? super T>>

implements SortedListInterface<T>

{

private Node<T> firstNode; // Reference to first node of chain

private int numberOfEntries;

public SortedLinkedListWithMode() {

this.firstNode = null;

this.numberOfEntries = 0;

} 

public T getMode()

{


T mode = null;

int modeCount = 0;

  

T arr[] = toArray();

int count = 0;

for(int i= 0 ; i<arr.length ; ++i) {

   count = 1;

   for(int j=i+1; j<arr.length ; ++j) {

       if(arr[i].compareTo(arr[j])==0)

           ++count;

   }

      

   if(count > modeCount) {

       modeCount = count;

       mode = arr[i];

   }

}



System.out.println("---> mode is " + mode + "; mode count is " + modeCount );

return mode;

}

public void add(T newEntry) {

Node<T> newNode = new Node(newEntry);

Node<T> nodeBefore = getNodeBefore(newEntry);

if (isEmpty() || (nodeBefore == null))

{

newNode.next = this.firstNode;

this.firstNode = newNode;

}

else

{ 

Node<T> nodeAfter = nodeBefore.next;

newNode.next = nodeAfter;

nodeBefore.next = newNode;

} 
this.numberOfEntries++;

} 

public boolean remove(T anEntry)

{

boolean found = false;

if (this.numberOfEntries > 0)

{

Node<T> nodeToRemove;

Node<T> 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<T> nodeAfter = nodeToRemove.next;

nodeBefore.next = nodeAfter;

} 

this.numberOfEntries--;

} // end if

} // end if

return found;

} // end remove

public int getPosition(T anEntry)

{

int position = 1;

Node<T> 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<T> nodeBefore = getNodeAt(givenPosition - 1);

Node<T> nodeToRemove = nodeBefore.next;

Node<T> 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<T> 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("\nThe 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();

}


private Node<T> getNodeBefore(T anEntry)

{

Node<T> currentNode = this.firstNode;

Node<T> nodeBefore = null;

while ( (currentNode != null) &&

(anEntry.compareTo(currentNode.data) > 0) )

{

nodeBefore = currentNode;

currentNode = currentNode.next;

} // end while

return nodeBefore;

} // end getNodeBefore

private Node<T> getNodeAt(int givenPosition)

{

assert !isEmpty() && (1 <= givenPosition) && (givenPosition <= this.numberOfEntries);

Node<T> 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 <S>

{

private S data; // Entry in list

private Node<S> 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<Integer> 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("\n*** Done ***");

} // end main

} // end LinkedSortedList

//---------

//------------------------------------------------------------------------------------------------------------------------

//SortedListInterface.java

//

//package Lab10;

public interface SortedListInterface<T extends Comparable<? super T>>

{

/** 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);



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

======================================================
See Output