Java Singly Linked List

Question

Here is a naive version of a singly linked list in Java. It implements only Collection and Iterable interfaces. Any comments and suggestions are welcome.

SinglyLinkedList.java:

package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

public class SinglyLinkedList<E> implements Collection<E>, Iterable<E> {
    private int size = 0;
    private Node<E> head = new Node<E>();
    // constructor
    public SinglyLinkedList() {
        head.setNext(head);
    }
    public SinglyLinkedList(Collection<E> c) {
        this();
        addAll(c);
    }
    // unmodifiable collection (except remove() method)
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> cursor = head;
            Node<E> previous = head;
            public boolean hasNext() {
                return cursor.getNext() != head;
            }
            public E next() {
                if (! hasNext()) {
                    throw new IndexOutOfBoundsException("Iterator has reached the end of the list!");
                }
                Node<E> toReturn = cursor.getNext();
                previous = cursor;
                cursor = toReturn;
                return toReturn.getInfo();
            }
            public void remove() { // only remove once the last node return by next() method.
                if (cursor == previous) {
                    throw new IndexOutOfBoundsException("Cannot remove current node. Last node returned by next() already removed, or reach the head of the list!");
                }
                previous.setNext(cursor.getNext());
                cursor.setNext(null);
                cursor = previous;
                size--;
            }
        };
    }
    public int size() {
        return size;
    }
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        Iterator<E> ite = iterator();
        sb.append("[");
        while (ite.hasNext()) {
            sb.append(ite.next());
            if (ite.hasNext()) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
    @SuppressWarnings("unchecked")
    public boolean contains(Object o) {
        if (o == null) {
            throw new NullPointerException("Object for contains() method is null!");
        }
        E ele = (E)o; // throw ClassCastException
        Iterator<E> ite = iterator();
        while (ite.hasNext()) {
            if (ite.next().equals(ele)) {
                return true;
            }
        }
        return false;
    }
    public boolean containsAll(Collection<?> c) {
        if (c == null) {
            throw new NullPointerException("Collection arg is null in conainsAll() method!");
        }
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }
    @SuppressWarnings("rawtypes")
    public boolean equals(Object o) {
        if (o == null || !(o instanceof SinglyLinkedList)) {
            return false;
        }
        SinglyLinkedList target = (SinglyLinkedList)o;
        if (size() != target.size()) {
            return false;
        }
        return hashCode() == target.hashCode();
    }
    public int hashCode() {
        int init = 31;
        for (E ele : this) {
            init = (init + ele.hashCode()) * 31;
        }
        return init;
    }
    public boolean isEmpty() {
        return head.getNext() == head;
    }
    public Object[] toArray() { // keep silence even if list is changed during the copy (naive way)
        Object[] array = new Object[size()];
        Iterator<E> ite = iterator();
        for (int i = 0; i <array.length; i++) {
            if (ite.hasNext()) {
                array[i] = ite.next();
            }
        }
        return Arrays.copyOf(array,array.length);  // deep copy, not shallow copy
    }
    public <T> T[] toArray(T[] a) {
        throw new UnsupportedOperationException("Not Yet!");
    }
    // modifible optional operations
    public boolean add(E e) { // add after head
        if (e == null) {
            return false;
        }
        Node<E> newNode = new Node<E>(e);
        newNode.setNext(head.getNext());
        head.setNext(newNode);
        size ++;
        return true;
    }
    public boolean addAll(Collection<? extends E> c) {
        boolean result = false;
        if (c == null || c.isEmpty()) {
            return result;
        }
        for (E ele : c) {
            if (add(ele)) {
                result = true;
            }
        }
        return result;
    }
    public void clear() {
        head.setNext(head);
        size = 0;
    }
    @SuppressWarnings("unchecked")
    public boolean remove(Object o) {
        boolean result = false;
        if (o == null) {
            Iterator<E> ite = iterator();
            while (ite.hasNext()) {
                if (ite.next() == null) {
                    ite.remove();
                    result = true;
                }
            }
        } else {
            E ele = (E)o;
            Iterator<E> ite = iterator();
            while (ite.hasNext()) {
                if (ite.next().equals(ele)) {
                    ite.remove();
                    result = true;
                }
            }
        }
        return result;
    }
    public boolean removeAll(Collection<?> c) {
        boolean result = false;
        if (c == null || c.isEmpty()) {
            return result;
        }
        if (!(c instanceof Collection)) {
            throw new ClassCastException("Argument for removeAll() method should be a Collection!");
        }
        for (Object o : c) {
            if (remove(o)) {
                result = true;
            }
        }
        return result;
    }
    public boolean retainAll(Collection<?> c) {
        boolean result = false;
        if (c == null || c.isEmpty()) {
            return result;
        }
        if (!(c instanceof Collection)) {
            throw new ClassCastException("Argument for retainAll() method should be a Collection!");
        }
        Iterator<E> ite = iterator();
        while (ite.hasNext()) {
            if (!c.contains(ite.next())) {
                ite.remove();
                result = true;
            }
        }
        return result;
    }
}

Node.java:

package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

public class Node<T> {
    private T info = null;
    private Node<T> next = null;

    public Node() {}
    public Node(T t) {
        info = t;
    }
    @SuppressWarnings("rawtypes")
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (o == null || !(o instanceof Node)) {
            return false;
        }
        Node node = (Node)o;
        return info.equals(node.info);
    }
    public int hashCode() {
        if (info == null) {
            return 0;
        }
        return info.hashCode();
    }
    public T getInfo() {
        return info;
    }
    public T setInfo(T t) { // return old value
        T old = getInfo();
        info = t;
        return old;
    }
    public Node<T> getNext() {
        return next;
    }
    public Node<T> setNext(Node<T> n) {
        Node<T> old = next;
        next = n;
        return old;
    }
    public String toString() {
        return "[" + info + "]";
    }
}

Answer 1

Advice 1

I would declare Node as the static private inner class in SinglyLinkedList:

public class SinglyLinkedList<E> ... {
    ...
    private static final class Node<E> {
        ...

Advice 2

In Node you have

private T info = null;

By default, Java sets reference members to null by default, so that you can write simply

private T info;

Advice 3

Name info is not the best possible; consider using data or datum.

Advice 4

public int hashCode() {
    if (info == null) {
        return 0;
    }
    return info.hashCode();
}

You can write the above more succintly:

public int hashCode() {
    return Objects.hashCode(info);
}

Advice 5

private int size = 0;

Integer fields are initialized to zero by default; write only

private int size;

Advice 6

private Node<E> head = new Node<E>();

Use diamond inference:

private Node<E> head = new Node<>();

Advice 7

public E next() {
    if (!hasNext()) {
        throw new IndexOutOfBoundsException("Iterator has reached the end of the list!");
    }
    ...

The correct exception is NoSuchElementException.

Advice 8

public void remove() { // only remove once the last node return by next() method.
    if (cursor == previous) {
        throw new IndexOutOfBoundsException("Cannot remove current node. Last node returned by next() already removed, or reach the head of the list!");
    ...

The correct exception here is IllegalStateException.

Advice 9

Your contains(Object o) throws a NullPointerException whenever o is null, java.util.ArrayList does not.

Advice 10

@SuppressWarnings("rawtypes")
public boolean equals(Object o) {
    if (o == null || !(o instanceof SinglyLinkedList)) {
        return false;
    }
    SinglyLinkedList target = (SinglyLinkedList) o;
    if (size() != target.size()) {
        return false;
    }
    return hashCode() == target.hashCode();
}

What??? If lists are equal in type and size you conclude that they are equal if they have same hash code? Unfortunately, there is a small chance that two different lists have same hash value, so do not rely on it. Instead, you could do:

public boolean equals(Object o) {
    if (o == null || !(o instanceof SinglyLinkedList)) {
        return false;
    }
    SinglyLinkedList<E> target = (SinglyLinkedList<E>) o;
    if (size() != target.size()) {
        return false;
    }

    Iterator<E> iter1 = iterator();
    Iterator<E> iter2 = target.iterator();

    while (iter1.hasNext()) {
        if (!Objects.equals(iter1.next(), iter2.next())) {
            return false;
        }
    }

    return true;
}

Advice 11

boolean remove(Object o) has wrong semantics: it removes all occurrences of o; Java lists remove only the first one.

Hope that helps.