Computing the size of a linked list using recursion/helper function - Java

Question

Beginner here using Java (first year student), and am unable to get the below function to work. The goal is to use recursion and a helper function to compute the size of a singly linked list. When running the code against test lists, it keeps returning List changed to [].

I'm struggling in general with Java, so any help is appreciated. Thank you

public class MyLinked {
  static class Node {
   public Node(double item, Node next) {
    this.item = item;
    this.next = next;
   }
   public double item;
   public Node next;
  }
  int N;
  Node first;

  public int sizeForward() {
   return sizeForwardHelper(first);
  }

  public int sizeForwardHelper(Node n) {
   Node current = first;
   if (current == null) {
    return 0;
   } else {
    first = first.next;
    return sizeForward() + 1;
   }
  }

I believe I have the first portion set up to return 0 if there are no elements in the List. I believe it's the second part that isn't setting up correctly?

Thanks

Answer 1

Because it’s important for your learning to not spoonfeed you, I’ll describe an approach rather than provide code.

Use this fact:

The length of the list from any given node to the end is 1 plus the length measured from the next node (if there is one).

Usually (as would work here), recursive functions take this form:

1. If the terminating condition is true, return some value
2. Otherwise, return some value plus the recursively calculated value

When writing a recursive function, first decide on the terminating condition. In this case, n == null is the obvious choice, and you’d return 0, because you’ve run off the end of the list and the length of nothing (ie no node) is nothing. This also handles the empty list (when first is null) without any special code.

Otherwise, return 1 (the length of one node) plus the length of next.

Put that all together and you’ll have your answer.

——

Hint: The body of the recursive helper method can be coded using one short line if you use a ternary expression.

Answer 2

Your method that computes the size of the list actually modifies the list in the process (with first = first.next; you set the first element to the next, and since there is a recursion, the first element always end up being null which is equivalent to an empty list with your design). Your method will work once, but your list will be empty afterwards.

To illustrate this, I added a print next to the instruction first = first.next; and wrote the following main:

public static void main(String[] args) {
    Node n2 = new Node(2d, null);
    Node n1 = new Node(1d, n2);
    Node n = new Node(0, n1);
    MyLinked l = new MyLinked(n);
    System.out.println("The first element is: "+l.first.item);
    System.out.println("The size is: "+l.sizeForward());
    System.out.println("The first element is: "+l.first);
}

It yields:

The first element is: 0.0
first is set to 1.0
first is set to 2.0
first is set to null
The size is: 3
The first element is: null

Clearly, you should not modify the list while computing its size. The helper method should return 0 if the node is null (empty list), and 1 plus the size of the rest of the list otherwise. Here is the code.

public int sizeForwardHelper(Node n) {
    if (n == null)
        return 0;
     else 
        return sizeForwardHelper(n.next) +1;
}

The goal of the arg free method sizeForward() is just to call the helper. The helper should not use it though.

Answer 3

Instead of calling your wrapper function call your helper function recursively. Try the following:

public int sizeForward () {
        return sizeForwardHelper (first);
}

public int sizeForwardHelper(Node n) {
      if (n == null) // base case
          return 0;
      return sizeForwardHelper(n.next) + 1; // count this node + rest of list
}