LinkedList implementation (+Sorted)

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> implements List {

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 elements) {
for (E element : elements) {
add(element);
}
return true;
}

@Override
public boolean addAll(int index, Collection elements) {
throw new UnsupportedOperationException();
}

@Override
public void clear() {
this.first = null;
}

@Override

• 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.

• 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.

• 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;

StackExchange Code Review Q#83264, answer score: 5