Java Linked List Problems

Question

I have two practice problems that I'm having trouble understanding. For # 1, the answer is that the list is printed in reverse, can anyone explain this to me? Also #7, why does the list begin to go backwards once it reaches the null? If anyone can provide some quick explanations it would be greatly appreciated, thanks!

1) What does the following function do for a given Linked List if we call it with the head node?

void method1(Node<T> node) {
  if(node == null)
    return;

  method1(node.getNext());
  System.out.println(node.getData().toString());
}

a. Prints the nodes of the linked list.

b. Prints the nodes of the linked list in reverse order.

c. Prints alternate nodes of the linked list.

d. Prints alternate nodes in reverse order.

Answer

b. Prints the nodes of the linked list in reverse order.

7) What is this method going to print, if we call it with the headnode of the linked list 1 → 2 → 3 → 4 → 5 → 6 ?

void method1(Node<Integer> node) {
  if (node == null)
    return;
  System.out.printf(“%d ”, node.getData());

  if (node.getNext() != null)
    method1(node.getNext().getNext());
  System.out.printf(“%d ”, node.getData());
}

a. 1 6 2 5 3 4

b. 1 3 5 6 4 2

c. 1 3 5 1 3 5

d. 1 3 5 5 3 1

Answer

c. 1 3 5 5 3 1

Answer 1

Question 1:

This is a recursive method call, meaning it continually calls itself until the break condition is met (in this case, there is no next node to move to). So, let's walk through this line by line.

void method1(Node<T> node) {
    if(node == null) // ends the recursive calls without doing anything extra
        return;

    method1(node.getNext()); // Do something with the next node before this node
    System.out.println(node.getData().toString()); // Print contents of current node.
}

As you can see, the first time we actually print anything is once we're at the end of the linked list (when node.next() returns null). After that first print, the calls move up the stack (and therefore backwards through the list), printing each node's contents as they go.

Question 2:

This is pretty much the same as question 1, just with some twists thrown in. First of all, we're printing the contents of the current node before and after the recursive call. So in effect, we'd be printing each node's contents in order, and then in reverse order. The slightly confusing part is that we're calling method1 on each node, but on every other node, meaning that we're skipping a node each time it's called.

So to summarize the answer to this question, we're effectively printing the contents of the current node, skipping one, printing the contents of the next one, etc... until we reach the end of the available nodes, then we just backtrace and print everything again (only this time in reverse order).

Answer 2

These are both easier to visualize if you draw out the call stack. These instructions are being executed sequentially, so I find it helpful to visualize the sequence of calls and call stack depth like this:

Question 1:

List = 1 → 2 → 3 → 4 → 5 → 6
method1(1)
  method1(2)
    method1(3)
      method1(4)
        method1(5)
          method1(6)
            method(null)
              return
            println(6)
          println(5)
        println(4)
      println(3)
    println(2)
  println(1)

The order of calls here can be seen from top to bottom. method1 is called before anything is printed. Once method1 hits the base case, it returns to the previous invocation, which in this case is the method1(6) invocation.

Each indentation here is another recursive call, and helps visualize the call stack. There are many very good answers explaining recursion better than I could (like this one on programmers.stackexchange.com).

Question 7:

You can do the same thing with this question:

1 → 2 → 3 → 4 → 5 → 6
method1(1)
  printf("%f ", 1)
  method1(3) // node.getNext().getNext() = 1 → 2 → 3
    printf("%f ", 3)
    method1(5)
      printf("%f ", 5)
      method1(null) // node.getNext().getNext() = 5 → 6
        return
      printf("%f ", 5)
    printf("%f ", 3)
  printf("%f ", 1)