Consider the LinkedBag class, which uses a linked nodes. What is the order of gr
ID: 3585055 • Letter: C
Question
Consider the LinkedBag class, which uses a linked nodes. What is the order of growth of the following methods for this class?
1. add(T)
2. remove()
3. remove(T)
4. contains(T)
-----------------------------------------------
LinkedBag.java
import java.util.Random;
/**
* A class of bags whose entries are stored in a chain of linked nodes. The bag
* is never full.
*/
public final class LinkedBag<T> 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 capacity of this bag.
*
* @return The integer number of entries that this bag can hold.
*/
public int getCapacity() {
return Integer.MAX_VALUE;
} // end getCapacity
/**
* 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 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;
} // 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
public T removeRandom() {
Random generator = new Random();
int position = generator.nextInt(numberOfEntries);
Node currentNode = firstNode;
int i=0;
while(i < position) {
currentNode = currentNode.next;
i++;
}
T randomDataToRemove = currentNode.data;
remove(randomDataToRemove);
return randomDataToRemove;
}
// for this equals method, two LinkedBags are equal
// if and only if their contents are the same and in
// the same order
// NOTE: this is different from how we implemented it
// in ArrayBag and is really only for an example
// of using linked nodes
@Override
public boolean equals(Object obj) {
if(obj instanceof LinkedBag) {
LinkedBag<T> otherBag = (LinkedBag) obj;
if(numberOfEntries == otherBag.numberOfEntries) {
Node currentNodeThisBag = firstNode;
Node currentNodeOtherBag = otherBag.firstNode;
while(currentNodeThisBag != null && currentNodeOtherBag != null) {
T currentDataThisBag = currentNodeThisBag.data;
T currentDataOtherBag = currentNodeOtherBag.data;
if(!currentDataThisBag.equals(currentDataOtherBag)) {
return false;
}
currentNodeThisBag = currentNodeThisBag.next;
currentNodeOtherBag = currentNodeOtherBag.next;
}
return true;
} else {
return false;
}
} else {
return false;
}
}
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
Consider the LinkedBag class, which uses a linked nodes. What is the order of growth of the following methods for this class?
1. add(T) : O(1) we just add to The Front of Linked List, we dont have to iterate till the end so its constant time
2. remove() : Removes first Node, Its O(1) we just remove The Front of Linked List, we dont have to iterate or fine till the end so its constant time , Head of the list i.e Front becomes the next element in list
3. remove(T) : First of all we need to search T and find its position in Linked list, Seaching itself takes O(n), if n is the length of linded list. Removal is O(1) just swapo pointers and make it null. Overall its O(N)
4. contains(T) we need to search T to know if it conatins in Linked list, Seaching itself takes O(N), if n is the length of linked list because in worst case we need to search till the end . Overall its O(N)
Thanks, let me know if there is any doubts
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.