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:
- First check if the element being attempted to be added is
null
. If it is, throw aNullPointerException
, as I want the list to be "null
-free" (Only becausenull
can't really be compared, because it will throw aNullPointerException
when attempting to compare). - Increment
size
. - Check if the list is empty (i.e. if the
first
Node itnull
) - 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. - 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:
- Is there a more efficient way of implementing what I am doing here?
- Are there some bad practices in there?
- What is the time-complexity of the methods? (Just want to find out)