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 + "]";
 }
}

• Alexander: It's so dense, why not space things out (vertically) a bit?
• weiShen: @Alexander ok, I will.
• David Foerster: 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.
• weiShen: Thanks @DavidFoerster , you have the point. Actually, I implement them all as an exercise when I read Thinking in Java ^^

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.

• weiShen: 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<>();
• coderodde: @weiShen Diamond inference is by no means mandatory, yet it saves some typing.