hi, i am trying out past year questions for a resit and am stuck with the question below.
Question 1

In the following you may assume the existence of the ListIterator<e> interface and LinkedList<E> class with the following methods

public interface ListIterator<E>
{
  E next();

  boolean hasNext();

}




public class LinkedList<E>
{

  public void addLast(E obj){..}

  public int size(){..}

  public ListIterator<E> listIterator(){...}

}

Finished the design of the printBackward method given below using the methods listed above in the ListIterator<E> interface and LinkedList<E> class. You should not introduce any new variable tinto the method. In your answer, do not copy the whole method. Write contents of the Initialisation 1, Initialisation 2, Block 1, Block 2, Block 3 . The printBackward method should be written recursive in a singly list backward. The parameter n specifies the size of the list.

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

           public void printBackward(int n)
           {

             if(n > 0){

              ListIterator<E> itr = /**Initialisation 1**/ list1.listIterator();

              int count = /**Initialisation 2**/  0;

              E item;

              while(itr.hasNext())
              {
                /**Block 1**/  addLast(list1); printBackward(); count --;

              }

                /**Block 2**/ E.next;
             }else

             /**Block 3**/ return;
           }
         }
         }

I have inserted my answers next to the /** ..**/ but am unsure if they are correct. It would be much appreciated if someone could help me correct my mistakes

The printBackward method should be written recursive in a singly list backward.

That's the keyword, recursive. :) Your implementation is not recursive but rather iterative. Do you know what recursive is?

Comments
I do, but am rather lost when it had to do with linkedList, truth be told am cramming for an exam tomorrow, and this question was in the past year...
 public void printBackward(int n)
     ...
     addLast(list1); printBackward(); count --;

Despite the missing parameter that looks like an attempt at recursion to me :)

Comments
Thanks, that is my attempt at recursion but am clueless on how to solve this.. :(

I think I did not grasp the basics of recursion properly, I could write simple recursion code but when it is anything to do with linkedList, I am just no good...

am cramming for an exam tomorrow

Ooops! Probably better to spend your time on a few other topics because you could burn a lot of hours trying to get this one straight.

ps: Anyone else know a good answer to this one? I can't see any sensible way to solve it within all the contraints.

Comments
thanks, :) but please try and help me, i really need to get this straight as exam is tomorrow and the pattern is always to fill in blocks of code.. :(

I am sorry that your recursive call is actually creating an infinite loop. From what I see there, my first thought about printBackward() method is that it would return a string. But then I saw addLast(), I believe that you would need to reverse the list before you manipulate with the list. Below is what I think what should happen...

ListIterator<E> itr = /**Initialisation 1**/ list1.listIterator();
LinkedList<E> backwardList = /**Initialisation 2**/ new LinkedList<E>();
createBackwardList(itr, backwardList);
// now the backwardList is containing backward linked list data

private void createBackwardList(ListIterator<E> itr, LinkedList<E> list) {
  if (itr.hasNext()) {    // has next item
    E item = itr.next();  // extract the item
    printBackward(itr, list);  // keep looking for the last item
    list.addLast(item);   // add back
  }
}

Look at the method createBackwardList(), it is a simple recursive method accepting the original list iterator and an empty list at first.

First, it check whether the iterator still contains more item, if so, get the item from the iterator and keep calling until it finds nothing in the list. Once it find nothing, each of the item that is extracted from the list will be added back to the empty list one by one from the last one it visited. Once it is done, the original empty list will be filled with backward list. Hope this help you understanding recursive...

"You should not introduce any new variable tinto the method. In your answer,", and it also imples no changes to the signature of the method, otherwize your solution is the (only) one I was considering

cool i don't even understand what it is. You are such a great person you have understand this computer language. :)

Hmm... I don't know if what the code portion he gave was the original... I mean I would rather want to see the empty shell of the code to work with. :) But well, that's one way I would solve the problem. :)

This article has been dead for over six months. Start a new discussion instead.