LinkedList implementation (+Sorted)

Question

I was recently learning about nodes and how they work in lists, and to test myself, I decided to write my own LinkedList implementation in Java. Then I decided, that since there is already a LinkedList out there, why not make it sorted? So now it is a SortedList.

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class SortedList<E extends Comparable<E>> implements List<E> {
 private Node first;
 private int size;
 public SortedList() {
 this.first = null;
 this.size = 0;
 }
 @Override
 public boolean add(E element) {
 if (element == null) {
 throw new NullPointerException();
 }
 size++;
 if (first != null) {
 Node before = null;
 Node current = first;
 for (; element.compareTo(current.getValue()) > 0; before = current, current = current
 .getNext()) {
 if(current.getNext() == null) {
 current.setNext(new Node(element));
 return true;
 }
 }
 Node newNode = new Node(element);
 if (before != null) {
 before.setNext(newNode);
 newNode.setNext(current);
 } else {
 newNode.setNext(first);
 first = newNode;
 }
 } else {
 first = new Node(element);
 }
 return true;
 }
 @Override
 public void add(int index, E element) {
 throw new UnsupportedOperationException();
 }
 @Override
 public boolean addAll(Collection<? extends E> elements) {
 for (E element : elements) {
 add(element);
 }
 return true;
 }
 @Override
 public boolean addAll(int index, Collection<? extends E> elements) {
 throw new UnsupportedOperationException();
 }
 @Override
 public void clear() {
 this.first = null;
 }
 @Override
 public boolean contains(Object obj) {
 return obj == null ? false : indexOf(obj) != -1;
 }
 @Override
 public boolean containsAll(Collection<?> elements) {
 for (Object element : elements) {
 if (!contains(element)) {
 return false;
 }
 }
 return true;
 }
 @Override
 public E get(int index) {
 if (index < 0 || index >= size) {
 throw new IndexOutOfBoundsException("The index " + index
 + " is out of range.");
 }
 Node result = first;
 for (; index > 0; index--, result = result.getNext())
 ;
 return result.getValue();
 }
 @Override
 public int indexOf(Object obj) {
 Node result = first;
 for (int i = 0; result != null; i++, result = result.getNext()) {
 if (result.getValue().equals(obj)) {
 return i;
 }
 }
 return -1;
 }
 @Override
 public boolean isEmpty() {
 return first == null;
 }
 @Override
 public Iterator<E> iterator() {
 return new SortedListIterator();
 }
 @Override
 public int lastIndexOf(Object obj) {
 Node result = first;
 int lastIndex = -1;
 for (int i = 0; result != null; i++, result = result.getNext()) {
 if (result.getValue().equals(obj)) {
 lastIndex = i;
 }
 }
 return lastIndex;
 }
 @Override
 public ListIterator<E> listIterator() {
 throw new UnsupportedOperationException();
 }
 @Override
 public ListIterator<E> listIterator(int startIndex) {
 throw new UnsupportedOperationException();
 }
 @Override
 public boolean remove(Object obj) {
 for (Node before = null, current = first; current != null; before = current, current = current
 .getNext()) {
 if (current.getValue().equals(obj)) {
 size--;
 if(before == null) {
 first = current.getNext();
 } else {
 before.setNext(current.getNext());
 }
 return true;
 }
 }
 return false;
 }
 @Override
 public E remove(int index) {
 if (index < 0 || index >= size) {
 throw new IndexOutOfBoundsException("The index " + index
 + " is out of range.");
 }
 Node removed = first;
 Node before = null;
 for (; index > 0; index--, before = removed, removed = removed
 .getNext())
 ;
 before.setNext(removed.getNext());
 size--;
 return removed.getValue();
 }
 @Override
 public boolean removeAll(Collection<?> elements) {
 boolean result = true;
 for (Object element : elements) {
 result &= remove(element);
 }
 return result;
 }
 @Override
 public boolean retainAll(Collection<?> elements) {
 boolean hasChanged = false;
 SortedList<E> result = new SortedList<E>();
 for (Object element : elements) {
 if (contains(element)) {
 result.add((E) element);
 hasChanged = true;
 }
 }
 if (hasChanged) {
 this.first = result.first;
 this.size = result.size;
 }
 return hasChanged;
 }
 @Override
 public E set(int index, E element) {
 throw new UnsupportedOperationException();
 }
 @Override
 public int size() {
 return size;
 }
 @Override
 public List<E> subList(int startIndex, int endIndex) {
 SortedList<E> result = new SortedList<E>();
 Node current = first;
 for (int i = 0; i < startIndex; current = current.getNext(), i++)
 ;
 result.first = new Node(current);
 for (int i = startIndex; i < endIndex; i++, current = current.getNext())
 ;
 current.setNext(null);
 return result;
 }
 @Override
 public Object[] toArray() {
 Object[] result = new Object[size];
 int counter = 0;
 for (Node current = first; current != null; current = current.getNext(), counter++) {
 result[counter] = current.getValue();
 }
 return result;
 }
 @Override
 public <T> T[] toArray(T[] array) {
 T[] result = array.length < size ? Arrays.copyOf(array, size) : array;
 int counter = 0;
 for (Node current = first; current != null; current = current.getNext(), counter++) {
 result[counter] = (T) current.getValue();
 }
 return result;
 }
 @Override
 public int hashCode() {
 final int prime = 31;
 int result = 1;
 result = prime * result + (first == null ? 0 : first.hashCode());
 result = prime * result + size;
 return result;
 }
 @Override
 public boolean equals(Object obj) {
 if (this == obj) {
 return true;
 }
 if (!(obj instanceof SortedList<?>)) {
 return false;
 }
 SortedList<?> other = (SortedList<?>) obj;
 if (size != other.size) {
 return false;
 }
 for(Iterator<?> thisIterator = this.iterator(), otherIterator = other.iterator(); thisIterator.hasNext() && otherIterator.hasNext();) {
 if(!thisIterator.next().equals(otherIterator.next())) {
 return false;
 }
 }
 return true;
 }
 @Override
 public String toString() {
 StringBuilder builder = new StringBuilder();
 for(Node current = first; current != null; current = current.getNext()) {
 builder.append(current.getValue().toString()).append(", ");
 }
 return builder.toString().substring(0, builder.length() - 2);
 }
 class Node {
 private E value;
 private Node next = null;
 public Node(E value) {
 this.value = value;
 }
 public Node(Node node) {
 this.value = node.value;
 this.next = node.next == null ? null : new Node(node.next);
 }
 public E getValue() {
 return value;
 }
 public void setValue(E value) {
 this.value = value;
 }
 public Node getNext() {
 return next;
 }
 public void setNext(Node next) {
 this.next = next;
 }
 @Override
 public int hashCode() {
 final int prime = 31;
 int result = 1;
 result = prime * result + ((next == null) ? 0 : next.hashCode());
 result = prime * result + ((value == null) ? 0 : value.hashCode());
 return result;
 }
 @Override
 public boolean equals(Object obj) {
 if (this == obj) {
 return true;
 }
 if (!(obj instanceof SortedList<?>.Node)) {
 return false;
 }
 SortedList.Node other = (SortedList.Node) obj;
 return this.equals(other)
 && (next == null ^ other.next == null)
 && next.equals(other.next)
 && (value == null ^ other.value == null)
 && value.equals(other.value);
 }
 }
 class SortedListIterator implements Iterator<E> {
 private Node current;
 public SortedListIterator() {
 this.current = first;
 }
 @Override
 public boolean hasNext() {
 return current != null;
 }
 @Override
 public E next() {
 E value = current.getValue();
 current = current.getNext();
 return value;
 }
 }
}

It is very simple: when you add an element, it will:

1. First check if the element being attempted to be added is null. If it is, throw a NullPointerException, as I want the list to be "null-free" (Only because null can't really be compared, because it will throw a NullPointerException when attempting to compare).
2. Increment size.
3. Check if the list is empty (i.e. if the first Node it null)
4. If it is, create a new Node with the value of the added element and set it as the first. Otherwise, loop through the elements in the list until one larger than the element attempt to be added is found. Then, add the element there.
5. return true.

Many of the methods in the class are based on one thing:

Node current = first;
for (int i = 0; i < startIndex; current = current.getNext(), i++)
 ;

or something similar.

Questions:

1. Is there a more efficient way of implementing what I am doing here?
2. Are there some bad practices in there?
3. What is the time-complexity of the methods? (Just want to find out)

Answer 1

1. Is there a more efficient way of implementing what I am doing here?

The way you keep the list sorted while adding elements is I think as fast as it gets with a linked list. If you were using a data structure that allows fast random access, then you could find the right insertion point faster by binary search, but then you'd pay the penalty of array copying when shifting the rest of the elements, so the overall benefit is questionable.

Keep in mind that if you have N elements and want them sorted, then it's faster to add them in a regular list and then sort the list. Sorting is typically bounded by \$O(N \log(N))\,ドル while keeping an automatically sorted list is bounded by \$O(N M)\$. If you really need the list sorted at all times, for example while adding items you also do other stuff that needs the list being built sorted, then your list is faster than re-sorting every time. I rarely see such situation in practice.

3. What is the time-complexity of the methods? (Just want to find out)

The methods other than add don't benefit from the fact that the list is sorted. For example indexOf (and contains using it), remove, and others will iterate until the end, even after a greater element is reached and therefore you could stop traversing the rest of the elements.

The worst-case complexity of methods that work with a single element like add, contains, remove is \$O(N)\$: you have to iterate over all elements. The optimization I suggested to use the sorted property everywhere won't change this.

The worst-case complexity of methods that work with a collection of elements like addAll, containsAll, removeAll is \$O(N M)\$ by the same reasoning, where \$N\$ is the size of the list, and \$M\$ is the number of the elements in the parameter.

2. Are there some bad practices in there?

for loops with empty body are not great. Especially if the loop condition contains multiple statements like this one:

 for (; index > 0; index--, before = removed, removed = removed
 .getNext())
 ;

It's more clear to convert this to a while loop instead:

 while (index > 0) {
 index--;
 before = removed;
 removed = removed.getNext();
 }

---

It's a subtle thing, but your sorting logic is not stable. It would be better to make it so.

Bugs

You have a couple of bugs that need to be corrected:

• toString crashes when the list is empty
• remove(0) crashes
• Node.equals crashes when next == null or value == null

Misc

In other implementations of List, toString returns values enclosed in [ ... ], for example [1, 2, 3, 3, 3, 4]. I recommend to do likewise.

I stumbled upon this when I wanted to write a unit test with assertEquals(Arrays.asList(...), yourList), realized that doesn't work because listIterator is not supported, so I tried to work around that with assertEquals(Arrays.asList(...).toString(), yourList.toString()). So I recommend to implement listIterator.

---

This can be simplified:

 return obj == null ? false : indexOf(obj) != -1;

To this:

 return obj != null && indexOf(obj) != -1;

Answer 2

The remove() and indexOf() methods can be improved. Here:

@Override
public boolean remove(Object obj) {
 for (Node before = null, current = first; current != null; before = current, current = current
 .getNext()) {
 if (current.getValue().equals(obj)) {
 size--;
 if (before == null) {
 first = current.getNext();
 } else {
 before.setNext(current.getNext());
 }
 return true;
 }
 }
 return false;
}

It can stop as soon as it reaches a larger element, and break out:

@Override
public boolean remove(Object obj) {
 for (Node before = null, current = first; current != null && current.getValue().compareTo((E) obj) < 0; before = current, current = current
 .getNext()) {
 if (current.getValue().equals(obj)) {
 size--;
 if (before == null) {
 first = current.getNext();
 } else {
 before.setNext(current.getNext());
 }
 return true;
 }
 }
 return false;
}

Same with indexOf(), which turns into:

@Override
public int indexOf(Object obj) {
 Node result = first;
 for (int i = 0; result != null && result.getValue().compareTo((E) obj) < 0; i++, result = result.getNext()) {
 if (result.getValue().equals(obj)) {
 return i;
 }
 }
 return -1;
}