(10 pts) In the RecursiveLL<E> class that we discussed in lecture, add recursive

Question

(10 pts) In the RecursiveLL<E> class that we discussed in lecture, add recursive methods for each of the following wrappers. Your recursive methods should add at least one parameter to keep track of the current node in the list. You can use the posted code as a starting point.

a. (2 pts) contains(E someItem) – returns true if someItem exists in the list, false if not.

b. (2 pts) search(E someItem) – returns the index of the first occurrence of someItem if it exists in the list, or -1 if someItem is not in the list.

c. (6 pts) reverse() – reverses the calling list. (Hint: write a recursive method that reverses the list starting from a specific node, returning the head of the reversed list.)

Explanation / Answer

HI, You have not posted Detailed Structure of RecursiveLL<E> class(as discussed in class).

I have implemented all methods based on some assumption.

Node head; is member of RecursiveLL class.

a. contains(E someItem) – returns true if someItem exists in the list, false if not.

   boolean contains(E someItem){
       return containsRecUtil(head, someItem);
   }

   boolean containsRecUtil(Node<E> node, E someItem){

       if(node == null)
           return false;
       if(node.getData().compareTo(someItem) == 0 )
           return true;
       return containsRecUtil(node.getNext(), someItem);

   }

b. search(E someItem) – returns the index of the first occurrence of someItem if it exists in the list,
or -1 if someItem is not in the list.

   int search(E someItem){
       return searchRecUtil(head, someItem, 0);
   }

   int searchRecUtil(Node<E> node, E someItem, int index){

       if(node == null)
           return -1;
       if(node.getData().compareTo(someItem) == 0 )
           return index;
       return containsRecUtil(node.getNext(), someItem, index+1);

   }

c. reverse() – reverses the calling list. (Hint: write a recursive method that reverses the list starting from a specific node, returning the head of the reversed list.)

   Node<E> reverse(){
       return reverseUtil(head);
   }

   public Node reverseUtil(Node list)
   {
   if (list == null) return null;

   if (list.getNext() == null) return list;
   // third question - in Lisp this is easy, but we don't have cons
   // so we grab the second element (which will be the last after we reverse it)

   Node<E> secondElem = list.getNext();

   // bug fix - need to unlink list from the rest or you will get a cycle
   list.setNext(null);

   // then we reverse everything from the second element on
   Node<E> reverseRest = reverseUtil(secondElem);

   // then we join the two lists
   secondElem.setNext(list);

   return reverseRest;
   }

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.