Return the number of elements in a linked list recursively

I have the following recursive method in a class called ImageNode which is passed the head(this - the start of the linked list) from a class called Image. I thought my code would recursively go through each node, increase the count then when its at the end return the count, unfortunatly not. Where am I going wrong?

private int countRec() {
    int count = 1;
    ImageNode node = this;

    if (node.next != null ){
        node = node.next;
        count++;
        countRec();
    }

    return count;
}
Jon Skeet
people
quotationmark

You're ignoring the result of countRec() - and you're iterating within the recursive call, defeating the purpose. (You're also making a recursive call on the same object, with no parameters and no change in state... so that can't do any good.) My recursive approach would be based on a design of:

  • If the next node is null, then the size of the list is 1
  • Otherwise, the size is 1 + the size from the next node onwards.

So:

private int countRec() {
    return next == null ? 1 : 1 + next.countRec();
}

Now that doesn't allow for a list of length 0 of course... you probably want to separate the idea of the list from the node, in which case the list class would have something like:

public int count() {
    return head == null ? 0 : head.countRec();
}

where the value of head is a reference to the head node if there is one, or null otherwise.

Of course, this will be O(n) in time and space. You can get O(1) space using iteration instead of recursion, and O(1) time by just keeping the size of the list as an instance variable in the list, updating it when you need to. I'm hoping that this question was based on an educational requirement rather than real code though - in production code, you'd just use the collections provided already.

people

See more on this question at Stackoverflow