When implementing BagInterface where the data is stored in a

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)

Solution

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;
   }