When implementing BagInterface, where the data is stored in an array, would it b
ID: 3930738 • Letter: W
Question
When implementing BagInterface, where the data is stored in an array, would it be more effective to remove from the beginning or the end of the array? Why? When implementing BagInterface, where the data is stored in a linked list, would it be more effective to remove from the beginning or the end of the linked list? Why? Implement remove method in liked list that removes an occurrence of a given entry from the bag. Return false if the removal is not successful. The header of the method is as follows: public boolean remove (T anEntry)Explanation / Answer
6)
SO, removal from end will be more efficient
Time : O(1)
remova from begining from an array means
you have to shift all other elements from second eleemnt
to till end, one by left (because first slot becomes empty after
removal of first one)
So, it takes O(n) time
7)
Removal from Begining is more efficient
Yes, because removing head node from a linked list is a
constant operation. You have to just change the head pointer to deconf element of list
Time: O(1)
Removal from end takes O(n) time
8)
public boolean remove(T anEntry){
T temp = firstNode;
// bag is empty
if(temp == null){
return false;
}
// if first element is equal to anEntry
if(temp.compareTo(anEntry) == 0){
firstNode = firstNode.getNext();
return true;
}
// traverse all other nodes and compare with anEntry
while(temp.getNext() != null){
// if next of tempis equal to anEntry
if(temp.getNext().compareTo(anEntry) == 0){
T t = temp.getNext();
temp.setNext(t.getNext());
return true;
}
temp = temp.getNext();
}
// we reach here means, anEntry is not in Bag
return false;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.