6
\$\begingroup\$

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 + "]";
    }
}
\$\endgroup\$
  • \$\begingroup\$ It's so dense, why not space things out (vertically) a bit? \$\endgroup\$ – Alexander - Reinstate Monica Jan 20 '17 at 1:23
  • \$\begingroup\$ @Alexander ok, I will. \$\endgroup\$ – weiShen Jan 20 '17 at 2:47
  • \$\begingroup\$ You could easily derive your list from AbstractList which implements some methods based on other abstract methods so you don't have to. Also, Collection<E> already extends Iterable<E>. There's no need for an explicit implements of the latter. \$\endgroup\$ – David Foerster Jan 20 '17 at 13:33
  • \$\begingroup\$ Thanks @DavidFoerster , you have the point. Actually, I implement them all as an exercise when I read Thinking in Java ^^ \$\endgroup\$ – weiShen Jan 20 '17 at 20:10
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot @coderodde, that does help! 11 advices are pertinent, each of them. And can you explain No.6, why diamond inference should be used? private Node<E> head = new Node<>(); \$\endgroup\$ – weiShen Jan 20 '17 at 21:07
  • \$\begingroup\$ @weiShen Diamond inference is by no means mandatory, yet it saves some typing. \$\endgroup\$ – coderodde Jan 20 '17 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.