Linked list mystery

Question

I'm trying to implement linked Lists. I therefore have this first class, called List, which represents one element

 package list;

/**
 * Linked list with int values.
 * 
 * The empty list is represented by a null reference.
 */
public class List {
    public int value;
    public List next;

    /**
     * Creates a new list
     * 
     * @param value value of the head of the list
     * @param next reference to rest of the list; may be null
     */
    public List(int value, List next) 
    {
        this.value = value;
        this.next = next;
    }   
}

and the linked list class itself which contains the following method

public static int size(List list)
    {
        if(list==null) return 0;
        else return size(list.next)+1;
    }

so far everything works. But if I try

public static int size(List list)
    {
        if(list.next==null) return 1;
        else return size(list.next)+1;
    }

i get a NullPointerException... I have no Idea why this shouldn't work since list.next should a one point be a reference to the null pointer and end the recursion. Therefore size(null.next) should never be called.

I apologise for the bad english and am grateful for any help

You're passing `list.next` to `size(..)` but `size(..)` checks for `list.next`. What are the possible values of `list`? — Sotirios Delimanolis, Mar 26 '14 at 17:08
I don't really get the question of the comment, but the values of list are either null (List list = null) or this (the list itself) — user2351468, Mar 26 '14 at 17:12
Well that would be the exception. But it should never go that far — user2351468, Mar 26 '14 at 17:20
"But it should never go that far" - why not? It is the very first thing your method does: `if(list.next==null) return 1;`. As the comment says - "The empty list is represented by a null reference" - so how does your method deal with an empty list? — davmac, Mar 26 '14 at 17:21
You were right. I forgot that it was possible to call the method on "uninitialised" lists — user2351468, Mar 26 '14 at 17:32

score 0 · Answer 1 · answered Mar 26 '14 at 17:12

0

That is because you call List.size(null). In the first version you checl for list==null, in the second you don't.

answered Mar 26 '14 at 17:12

Axel

13,939
5
50
79

let's say I have three elements 2->1->null. At 1 the 1.next should give the null pointer and therefore list.size(null) should never be called? – user2351468 Mar 26 '14 at 17:13
You gave the example in your own answer. Note the capital `L` to denote the call of the static method. – Axel Mar 26 '14 at 19:31

kiruwka · Accepted Answer · 2014-03-26T17:37:21.737

0

Your original size method handles null argument fine.
The second version does not.
The second version would only give NPE if you call List.size(null), for all non-null inputs, it should behave absolutely similarly.

Therefore, just add if (list == null) return 0; to your second version.

I really suggest that you declare size() a as member method:

public int size() {
    return next == null ? 1 : next.size() + 1;
}

so you can call : new List(1, null).size();

edited Mar 26 '14 at 17:37

answered Mar 26 '14 at 17:12

kiruwka

9,250
4
30
41

I know but I don't know where the error is :) – user2351468 Mar 26 '14 at 17:16
Well, normally you should not get this, could you give the test input for your `NPE` ? – kiruwka Mar 26 '14 at 17:20
Oh that's it! It is actually possible to check the size of uninitialised lists and therefore null.next can be called. – user2351468 Mar 26 '14 at 17:25

user2351468 · Answer 3 · 2014-03-26T17:39:53.033

0

The answer was inspired by a previous comment.

It is actually possible to do this

List list = null;
LinkedList.size(list);

and therefore if the list is uninitialised null.next can be called. In other words: my list has to have at least two elements (firstelement and null)!

edited Mar 26 '14 at 17:39

answered Mar 26 '14 at 17:28

user2351468

39
4

This code won't work according to sample in the question. You should supply parameter to your `size` method. And yes, it is very confusing usage of your `static` size method, therefore I suggest that you make it member method instead. – kiruwka Mar 26 '14 at 17:32

Linked list mystery

3 Answers3