public final class LinkedBag1<T> implements BagInterface<T> { private class Node
ID: 3874191 • Letter: P
Question
public final class LinkedBag1<T> implements BagInterface<T> {
private class Node {
private T data; // Entry in bag
private Node next; // Link to next node
public Object item;
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node nextNode) {
data = dataPortion;
next = nextNode;
} // end constructor
} // end Node
private Node firstNode; // Reference to first node
private int numberOfEntries;
public LinkedBag1() {
firstNode = null;
numberOfEntries = 0;
} // end default constructor
/**
* Adds a new entry to this bag.
*
* @param newEntry The object to be added as a new entry.
* @return True.
*/
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 Object[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;
// Note: The body of this method could consist of one return statement,
// if you call Arrays.copyOf
} // end toArray
/**
* Sees whether this bag is empty.
*
* @return True if the 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 the bag.
*/
public int getCurrentSize() {
return numberOfEntries;
} // end getCurrentSize
// STUBS:
/**
* Removes one unspecified entry from this bag, if possible.
*
* @return Either the removed entry, if the removal was successful, or null.
*/
public T remove() {
if(isEmpty()) {
return null;
} else {
T result = firstNode.data;
numberOfEntries--;
firstNode = firstNode.next;
return result;
}
} // end remove
/**
* Removes one occurrence of a given entry from this bag.
*
* @param anEntry The entry to be removed.
* @return True if the removal was successful, or false otherwise.
*/
public boolean remove(T anEntry) {
//First: find the correct node
Node currNode = firstNode;
while(currNode != null) {
if(currNode.data.equals(anEntry)) {
currNode.data = firstNode.data;
firstNode = firstNode.next;
numberOfEntries--;
return true;
}
currNode = currNode.next;
}
return false;
} // end remove
/** Removes all entries from this bag. */
public void clear() {
while(!isEmpty()) {
remove();
}
} // end clear
/**
* 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 the bag.
*/
public int getFrequencyOf(T anEntry) {
T result = firstNode.data;
int count = 0;
for(int i = 0; i < numberOfEntries; i++) {
if(anEntry.equals(result))
count ++;
}
return count;
} // 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;
}
return found;
} // end contains
private Node find(T anEntry) {
Node currNode = firstNode;
while(currNode != null) {
if(currNode.data.equals(anEntry)) {
return currNode;
}
}
return null;
}
public boolean addRear(T anEntry) {
Node currNode = firstNode;
while(currNode != null) {
if(currNode.next.equals(null)) {
T newEntry = null;
Node newNode = new Node(newEntry);
}
LinkedBag1<T>.Node newNode = null;
currNode.next = newNode;
}
return false;
}
public boolean removeAll(T anEntry) {
return false;
}
public boolean myequals(LinkedBag1<T> other) {
return false;
}
public LinkedBag1<T> intersection(LinkedBag1<T> other) {
LinkedBag1<T> result = new LinkedBag1<T>();
//result.add(newEntry);
return result;
}
Explanation / Answer
public final class LinkedBag1<T> implements BagInterface<T> {
private class Node {
private T data; // Entry in bag
private Node next; // Link to next node
public Object item;
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node nextNode) {
data = dataPortion;
next = nextNode;
} // end constructor
} // end Node
private Node firstNode; // Reference to first node
private int numberOfEntries;
public LinkedBag1() {
firstNode = null;
numberOfEntries = 0;
} // end default constructor
/**
* Adds a new entry to this bag.
*
* @param newEntry The object to be added as a new entry.
* @return True.
*/
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 Object[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;
// Note: The body of this method could consist of one return statement,
// if you call Arrays.copyOf
} // end toArray
/**
* Sees whether this bag is empty.
*
* @return True if the 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 the bag.
*/
public int getCurrentSize() {
return numberOfEntries;
} // end getCurrentSize
// STUBS:
/**
* Removes one unspecified entry from this bag, if possible.
*
* @return Either the removed entry, if the removal was successful, or null.
*/
public T remove() {
if(isEmpty()) {
return null;
} else {
T result = firstNode.data;
numberOfEntries--;
firstNode = firstNode.next;
return result;
}
} // end remove
/**
* Removes one occurrence of a given entry from this bag.
*
* @param anEntry The entry to be removed.
* @return True if the removal was successful, or false otherwise.
*/
public boolean remove(T anEntry) {
//First: find the correct node
Node currNode = firstNode;
while(currNode != null) {
if(currNode.data.equals(anEntry)) {
currNode.data = firstNode.data;
firstNode = firstNode.next;
numberOfEntries--;
return true;
}
currNode = currNode.next;
}
return false;
} // end remove
/** Removes all entries from this bag. */
public void clear() {
while(!isEmpty()) {
remove();
}
} // end clear
/**
* 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 the bag.
*/
public int getFrequencyOf(T anEntry) {
T result = firstNode.data;
int count = 0;
for(int i = 0; i < numberOfEntries; i++) {
if(anEntry.equals(result))
count ++;
}
return count;
} // 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;
}
return found;
} // end contains
private Node find(T anEntry) {
Node currNode = firstNode;
while(currNode != null) {
if(currNode.data.equals(anEntry)) {
return currNode;
}
}
return null;
}
public boolean addRear(T anEntry) {
Node currNode = firstNode;
while(currNode != null) {
if(currNode.next.equals(null)) {
T newEntry = null;
Node newNode = new Node(newEntry);
}
LinkedBag1<T>.Node newNode = null;
currNode.next = newNode;
}
return false;
}
public boolean removeAll(T anEntry) {
Node currNode = firstNode;
while(currNode != null) {
if(currNode.data.equals(anEntry)) {
currNode.data = firstNode.data;
firstNode = firstNode.next;
numberOfEntries--;
}
currNode = currNode.next;
}
return true;
}
public boolean myequals(LinkedBag1<T> other) {
if(this.getCurrentSize() != other.getCurrentSize())
return false;
Node a = this.firstNode;
Node b = other.firstNode;
while(a!=null && b!=null && a.data.equals(b.data)){
a = a.next;
b = b.next;
}
if(a==null && b==null)
return true;
return false;
}
public LinkedBag1<T> intersection(LinkedBag1<T> other) {
Node currNode = this.firstNode;
Node curr = other.firstNode;
LinkedBag1<T> result = new LinkedBag1<T>();
while (currNode != null)
{
if (other.contains(currNode.data))
result.add(currNode.data);
curr = curr.next;
}
return result;
}
}
========
I have implemented remaining methods, please check
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.