Linked List

package iteration;

public interface Iterable {
    public Iterator iterator();
}

package dataStructures;

import iteration.Iterable;

public interface List extends Iterable {
    public void insert(int index, Object value)
            throws IndexOutOfBoundsException;
    public void add(Object value);
    public Object delete(int index) throws IndexOutOfBoundsException;
    public boolean delete(Object value);
    public void clear();
    public Object set(int index, Object value)
            throws IndexOutOfBoundsException;
    public Object get(int index) throws IndexOutOfBoundsException;
    public int indexOf(Object value);
    public boolean contains(Object value);
    public int size();
    public boolean isEmpty();
}

package sorting;

import dataStructures.List;

public interface ListSorter {
    public List sort(List list);
}

package iteration;

public interface Iterator {
    public void first();
    public void last();
    public boolean isDone();
    public void next();
    public void previous();
    public Object current() throws IteratorOutOfBoundsException;
}

package iteration;

public class ArrayIterator implements Iterator {
    private final Object[] _array;
    private final int _first;
    private final int _last;
    private int _current = -1;

    public ArrayIterator(Object[] array, int start, int length) {
        assert array != null : "array can’t be null";
        assert start >= 0 : "start can’t be < 0";
        assert start < array.length : "start can’t be > array.length";
        assert length >= 0 : "length can’t be < 0";
        _array = array;
        _first = start;
        _last = start + length - 1;
        assert _last < array.length : "start + length can’t be > array.length";
    }

    public ArrayIterator(Object[] array) {
        assert array != null : "array can’t be null";
        _array = array;
        _first = 0;
        _last = array.length - 1;
    }

    public void first() {
        _current = _first;
    }

    public void last() {
        _current = _last;
    }

    public void next() {
        ++_current;
    }

    public void previous() {
        --_current;
    }

    public boolean isDone() {
        return _current < _first || _current > _last;
    }

    public Object current() throws IteratorOutOfBoundsException {
        if (isDone()) {
            throw new IteratorOutOfBoundsException();
        }
        return _array[_current];
    }
}

package iteration;

public class IteratorOutOfBoundsException extends RuntimeException {
}

package dataStructures;

import iteration.Iterator;
import iteration.IteratorOutOfBoundsException;

public class LinkedList implements List {
    private final Element _headAndTail = new Element(null);
    private int _size;

    public LinkedList() {
        clear();
    }

    private static final class Element {
        private Object _value;
        private Element _previous;
        private Element _next;

        public Element(Object value) {
            setValue(value);
        }

        public void setValue(Object value) {
            _value = value;
        }

        public Object getValue() {
            return _value;
        }

        public Element getPrevious() {
            return _previous;
        }

        public void setPrevious(Element previous) {
            assert previous != null : "previous can’t be null";
            _previous = previous;
        }

        public Element getNext() {
            return _next;
        }

        public void setNext(Element next) {
            assert next != null : "next can’t be null";
            _next = next;
        }

        public void attachBefore(Element next) {
            assert next != null : "next can’t be null";
            Element previous = next.getPrevious();
            setNext(next);
            setPrevious(previous);
            next.setPrevious(this);
            previous.setNext(this);
        }

        public void detach() {
            _previous.setNext(_next);
            _next.setPrevious(_previous);
        }
    }

    public void insert(int index, Object value)
            throws IndexOutOfBoundsException {
        assert value != null : "value can’t be null";
        if (index < 0 || index > _size) {
            throw new IndexOutOfBoundsException();
        }
        Element element = new Element(value);
        element.attachBefore(getElement(index));
        ++_size;
    }
    private Element getElement(int index) {
        Element element = _headAndTail.getNext();
        for (int i = index; i > 0; --i) {
            element = element.getNext();
        }
        return element;
    }

    public void add(Object value) {
        insert(_size, value);
    }

    public Object get(int index) throws IndexOutOfBoundsException {
        checkOutOfBounds(index);
        return getElement(index).getValue();
    }
    public Object set(int index, Object value)
            throws IndexOutOfBoundsException {
        assert value != null : "value can’t be null";
        checkOutOfBounds(index);
        Element element = getElement(index);
        Object oldValue = element.getValue();
        element.setValue(value);
        return oldValue;
    }

    private void checkOutOfBounds(int index) {
        if (isOutOfBounds(index)) {
            throw new IndexOutOfBoundsException();
        }
    }

    private boolean isOutOfBounds(int index) {
        return index < 0 || index >= _size;
    }

    public int indexOf(Object value) {
        assert value != null : "value can’t be null";
        int index = 0;
        for (Element e = _headAndTail.getNext();
             e != _headAndTail;
             e = e.getNext()) {
            if (value.equals(e.getValue())) {
                return index;
            }
            ++index;
        }
        return -1;
    }

    public boolean contains(Object value) {
        return indexOf(value) != -1;
    }

    public Object delete(int index) throws IndexOutOfBoundsException {
        checkOutOfBounds(index);
        Element element = getElement(index);
        element.detach();
        --_size;
        return element.getValue();
    }

    public boolean delete(Object value) {
        assert value != null : "value can’t be null";
        for (Element e = _headAndTail.getNext();
             e != _headAndTail;
             e = e.getNext()) {
            if (value.equals(e.getValue())) {
                e.detach();
                --_size;
                return true;
            }
        }
        return false;
    }

    private final class ValueIterator implements Iterator {
        private Element _current = _headAndTail;
        public void first() {
            _current = _headAndTail.getNext();
        }
        public void last() {
            _current = _headAndTail.getPrevious();
        }
        public boolean isDone() {
            return _current == _headAndTail;
        }
        public void next() {
            _current = _current.getNext();
        }
        public void previous() {
            _current = _current.getPrevious();
        }
        public Object current() throws IteratorOutOfBoundsException {
            if (isDone()) {
                throw new IteratorOutOfBoundsException();
            }
            return _current.getValue();
        }
    }

    public Iterator iterator() {
        return new ValueIterator();
    }

    public int size() {
        return _size;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public void clear() {
        _headAndTail.setPrevious(_headAndTail);
        _headAndTail.setNext(_headAndTail);
        _size = 0;
    }
}