public final class LinkedBag1 implements BagInterface {

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.Node newNode = null;

currNode.next = newNode;

}

return false;

}

public boolean removeAll(T anEntry) {

return false;

}

public boolean myequals(LinkedBag1 other) {

return false;

}

public LinkedBag1 intersection(LinkedBag1 other) {

LinkedBag1 result = new LinkedBag1();

//result.add(newEntry);

return result;

}