Question 1. Write a method to determine if a linked chain of Integers are all di
ID: 3727085 • Letter: Q
Question
Question 1. Write a method to determine if a linked chain of Integers are all divisible by some number. The method header is:
public static boolean isDivisibleBy(Node<Integer> firstNode, int divisor)
Examples:
Invoking the method with 3 -> 9 -> 6-> 12 and 3 returns true.
Invoking with 3 -> 9 -> 15 -> 8 -> 6 and 3 returns false.
Question 2. Write a method to print every other node in the chain, starting with the first node. The method header is:
Examples:
Invoking the method with 3->9->6->12 will print the values 3 and 6
Invoking the method with 3->9->6->12->8 will print the values 3, 6, and 8
Question 3. Write a getMin method for the LinkedBag class. This method returns the smallest object in the bag.
Assume the bag contains objects whose classes implement Comparable.
This means you can invoke compareTo on your objects of type T.
Do not invoke the toArray() method and do not use a separate ArrayList, LinkedList, etc. type object.
Notes:
When writing for LinkedBag and LList, you are writing from the implementation perspective.
That means your code would go inside of these classes, which means you have access to private instance data variables and private methods from those classes.
Often, accessing the linked nodes directly allows you to write a much more efficient solution.
Avoid writing code that involves a nested looping through a linked chain.
Often times this will happen when you have a loop to go through the chain and then you invoke a method inside that loop that also involves a loop- this results in a nested loop. (Very inefficient!)
Calls to methods like getNodeAt, getEntry, add, or contains within a loop that iterates through the list result in inefficient code.
LinkedBag.java
public final class LinkedBag<T extends Comparable> implements BagInterface<T> {
private Node firstNode; // Reference to first node
private int numberOfEntries;
public LinkedBag() {
firstNode = null;
numberOfEntries = 0;
} // end default constructor
/**
* Sees whether this bag is empty.
*
* @return True if this bag is empty, or false if not.
*/
public boolean isEmpty() {
return numberOfEntries == 0;
} // end isEmpty
/**
* Gets the number of entries currently in this bag.
*
* @return The integer number of entries currently in this bag.
*/
public int getCurrentSize() {
return numberOfEntries;
} // end getCurrentSize
/**
* Adds a new entry to this bag.
*
* @param newEntry
* The object to be added as a new entry
* @return True if the addition is successful, or false if not.
*/
public boolean add(T newEntry) // OutOfMemoryError possible
{
// Add to beginning of chain:
Node newNode = new Node(newEntry);
newNode.next = firstNode; // Make new node reference rest of chain
// (firstNode is null if chain is empty)
firstNode = newNode; // New node is at beginning of chain
numberOfEntries++;
return true;
} // end add
/**
* Retrieves all entries that are in this bag.
*
* @return A newly allocated array of all the entries in this bag.
*/
public T[] toArray() {
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Comparable[numberOfEntries]; // Unchecked cast
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null)) {
result[index] = currentNode.data;
index++;
currentNode = currentNode.next;
} // end while
return result;
} // end toArray
/**
* Counts the number of times a given entry appears in this bag.
*
* @param anEntry
* The entry to be counted.
* @return The number of times anEntry appears in this bag.
*/
public int getFrequencyOf(T anEntry) {
int frequency = 0;
int counter = 0;
Node currentNode = firstNode;
while ((counter < numberOfEntries) && (currentNode != null)) {
if (anEntry.equals(currentNode.data)) {
frequency++;
} // end if
counter++;
currentNode = currentNode.next;
} // end while
return frequency;
} // end getFrequencyOf
/**
* Tests whether this bag contains a given entry.
*
* @param anEntry
* The entry to locate.
* @return True if the bag contains anEntry, or false otherwise.
*/
public boolean contains(T anEntry) {
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null)) {
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while
return found;
} // end contains
// Locates a given entry within this bag.
// Returns a reference to the node containing the entry, if located,
// or null otherwise.
private Node getReferenceTo(T anEntry) {
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null)) {
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while
return currentNode;
} // end getReferenceTo
/** Removes all entries from this bag. */
public void clear() {
while (!isEmpty())
remove();
} // end clear
/**
* Removes one unspecified entry from this bag, if possible.
*
* @return Either the removed entry, if the removal was successful, or null.
*/
public T remove() {
T result = null;
if (firstNode != null) {
result = firstNode.data;
firstNode = firstNode.next; // Remove first node from chain
numberOfEntries--;
} // end if
return result;
} // end remove
/**
* Removes one occurrence of a given entry from this bag, if possible.
*
* @param anEntry
* The entry to be removed.
* @return True if the removal was successful, or false otherwise.
*/
public boolean remove(T anEntry) {
boolean result = false;
Node nodeN = getReferenceTo(anEntry);
if (nodeN != null) {
nodeN.data = firstNode.data; // Replace located entry with entry in
// first node
firstNode = firstNode.next; // Remove first node
numberOfEntries--;
result = true;
} // end if
return result;
} // end remove
private class Node {
private T data; // Entry in bag
private Node next; // Link to next node
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node nextNode) {
data = dataPortion;
next = nextNode;
} // end constructor
} // end Node
} // end LinkedBag
Explanation / Answer
Please find the code of the above three methods below with detailed inline comments.
CODE
=====================
/**
* determine if a linked chain of Integers are all divisible by some number.
* @param firstNode
* @param divisor
* @return True of all the Integers are divisible by divisor, else false
*/
public boolean isDivisibleBy(Node<Integer> firstNode, int divisor) {
Node<Integer> temp = firstNode; // initialize temp to firstNode
while(temp != null) {
if(temp.data % divisor != 0)
return false;
}
return true;
}
/**
* print every other node in the chain, starting with the first node.
*/
public void printEveryOther(Node<T> firstNode) {
Node<T> temp = firstNode; // initialize temp to firstNode
// Loop through every alternate node in the list
while(temp != null && temp.next != null) {
System.out.print(temp.data + " ");
temp = temp.next.next;
}
}
/**
*
* @param firstNode
* @return the smallest element in the Bag
*/
public T getMin(Node<T> firstNode) {
Node<T> temp = firstNode; // initialize temp to firstNode
T min = temp.data;
// LOOP through all the elements in the Bag
while(temp != null) {
// Move temp to next element
temp = temp.next;
// compare temp.data with min element. If min > temp.data,
// min.compareTo(temp.data) return 1
if(min.compareTo(temp.data) == 1)
// update min
min = temp.data;
}
return min;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.