Question

JAVA

Write Java code for extending the LinkedList class of java.util.* to ExtLinkedList that would include the following method: public ExtLinkedList firstHalfList() which returns the first half of the list. In other words, if you have a ExtLinkedList of size 5, for example, the method firstHalfList should return the list with the first two nodes. If it is a list of size 6, it should return the list with the first three nodes. The original list should not be modified. Also, note that the numbers 5 and 6 are only provided for illustration purposes – your code should work for any size including the empty list and any parameter E. Also, the original LinkedList should remain intact and not have half its contents deleted. Estimate the run-time complexity of the method given the size of the original list is n.

Answer 1

package learning;

import java.util.LinkedList;

/***
*Making a new class ExtLinkedList which will extend LinkedList and
*making it generic so that it can work for any type of list
*/

public class ExtLinkedList<E> extends LinkedList<E>{

/***
*
* @return new List which will be half of the original list
*/

public ExtLinkedList<E> firstHalfList(){
  // Create the list which will contain the half of the elements of original list
  ExtLinkedList<E> firstHalf = new ExtLinkedList<E>();
  // First size needs to be find of the original list
  int size = this.size();
  for(int i =0; i < (size)/2 ; i++){ //
   firstHalf.add(this.get(i));
  }
  return firstHalf;
}


public static void main(String args[]){
  ExtLinkedList<String> myList = new ExtLinkedList<String>();
  myList.add("Nitin");
  myList.add("Maryada");
  myList.add("Bunty");
  myList.add("Sachin");
  myList.add("AAni");
  myList.add("Saumil");
  System.out.println("New Half List is: " + myList.firstHalfList());
  System.out.println("Original List: " + myList);
}

}

/**** Run time Compexity will be o(n) as we will be traversing n/2 elements ***/