Implementing a set using a linked list

Question

My task is to add the specified element to the linked list if it is not already present

/**
* Adds the specified element to this set if it is not already present.
* @param o element to be added to this set.
* @return  true if this set did not already contain the specified element.
* @throws NullPointerException - if the specified element is null and this set  does 
  not support null elements
 */

This is my solution

public boolean add(E o)  {

    if (o == null)
        throw new NullPointerException();

    ListNode newNode = new ListNode(o, null);
    if (contains(o))
    {
     return false;
    }
    else {

    head.next=newNode;
    head=newNode;
    return true;
   }     
}

Can please anybody check it and correct if there are mistakes, or give hints to correct it?

Answer 1

Let's say that you are starting with a list containing five elements:

$$ \newcommand{ptr}[1]{\overset{\mathtt{#1}}{\longrightarrow}} \mathtt{head} \ptr{} \fbox{first} \ptr{next} \fbox{second} \ptr{next} \fbox{rest} \ptr{next} \fbox{of} \ptr{next} \fbox{list} \ptr{next} \mathtt{null} $$

Then, you add a non-duplicate item called "another". After executing head.next=newNode:

$$ % "align" allows us to do vertical alignment % "\\" separates lines % "&" is an alignment marker. The markers in different rows % are positioned above each other, and horizontally centered. \newcommand{ptr}[1]{\overset{\mathtt{#1}}{\longrightarrow}} \begin{align*} &\mathtt{newNode} \\ &\quad\downarrow \\ \mathtt{head} \ptr{} \fbox{first} \ptr{next} &\fbox{another} \ptr{next} \mathtt{null} \\ &\fbox{second} \ptr{next} \fbox{rest} \ptr{next} \fbox{of} \ptr{next} \fbox{list} \ptr{next} \mathtt{null} \end{align*} $$

You've just orphaned and discarded everything starting from the second element. Then it gets worse when you set head=newNode.

Answer 2

The first big problem I see is readability. Your code is missing good indentation and the style does not conform with what I'm used to seeing. Your code would read better like this:

public boolean add(E o)  {
    if (o == null) {
        throw new NullPointerException();
    }

    ListNode newNode = new ListNode(o, null);

    if (contains(o)) {
        return false;
    } else {
        head.next=newNode;
        head=newNode;
        return true;
   }     
}

I've removed some of the unneeded white space lines, since it was creating some weird space in the code. This can be considered style, but you should try to come up with something that feels natural.

Brackets {} have a standard in Java; you should follow it.

I've added brackets to the if with the throw exception. Note that this is optional and a matter of personal style.

---

Another thing that you could do is reorganize the method a bit. At the moment, you first verify if o is null, then you create newNode and after you check if o is already in the list. If o is in the list, you return false from the method and the new node will be discarded. So why would you create newNode if you're not sure if you will use it later on?

One option could be to move ListNode newNode = new ListNode(o, null); to the else block. You could also remove the else part and move the if (contains(o)) just before the initialization, leaving something like this:

public boolean add(E o) {
    if (o == null) {
        throw new NullPointerException();
    }

    if (contains(o)) {
        return false;
    }

    ListNode newNode = new ListNode(o, null);
    head.next = newNode;
    head = newNode;
    return true;
}

Answer 3

There are a few inconsistencies in your JavaDoc comments (bravo! for using them):

• Parameter and exception descriptions don't need to be complete sentences and should not end with a period. This helps keep them short, too.
• Omit the - after the exception type. These lines should look just like the @param lines.
• It's typical to indent the * one space extra so the asterisks form a corner, and make sure every line has an asterisk.
• I like to place a blank line between the method's description and the first attribute (@param in this case), but that's a personal style chosen to aid my poor vision.

Taking these all together produces this:

/**
 * Adds the specified element to this set if it is not already present.
 *
 * @param o element to be added to this set.
 * @return true if this set did not already contain the specified element
 * @throws NullPointerException if the specified element is null
 *         and this set does not support null elements
 */

Since this set doesn't support null elements, you can drop the "and this set does not support null elements" at the end.

Answer 4

throw new NullPointerException();

The other reviewers cover other bits sufficiently well, so I just want to point out how odd this looks.

A null pointer exception typically occurs when you try to access a null Object using the dot operator. Ie:

Object obj = null;
obj.toString(); // NullPointerException!!!

In your case, however, you're not accessing an object. You're simply checking if it's null or not.

Also, the rule of thumb is that exceptions should only be thrown when something exceptionally bad happens. Is receiving a null object in this function exceptionally bad? (That's for you to decide). If you regularly expect attempts to insert null objects, then I would say that throwing an exception is extreme, and you should just return false instead.

Also, the javadoc:

@throws NullPointerException - if the specified element is null and this set does not support null elements

David Harkness pointed this out, but I'll reiterate since I'm on the exception anyway. You say "and this set does not support null elements", which either suggests some sets can have a null element, or you're saying that this set class doesn't allow null elements. If some sets are allowed a null element, you need to change your if statement to this:

if (o == null && !isNullSupported()) {
    throw new NullPointerException();
}

Regardless, this bit of documentation would be more fitting in the class' javadoc instead of in this exception's javadoc. Knowing whether a collection takes null values or not is one of the first things people will want to know when they use your code.

Answer 5

The "else" part of the if-else is redundant, since the if contains a return statement.

Also what happens when you add the first element? If head is null, the head.next=newNode line will give a NullPointerException.