public class LinkedList<E> implements List<E> {

    private static class Elem<T> {

        private T value;

        private Elem<T> previous;
        private Elem<T> next;

        private Elem( T value, Elem<T> previous, Elem<T> next ) {
            this.value = value;
            this.previous = previous;
            this.next = next;
        }
    }

    private Elem<E> head;
    private int size;

    public LinkedList() {
        head = new Elem<E>( null, null, null );
        head.next = head.previous = head; // circularize
        size = 0;
    }

    public int size() {
        return size;
    }

    public E get( int pos ) {

        if ( pos < 0 || pos >= size ) {
            throw new IndexOutOfBoundsException( Integer.toString( pos ) );
        }

        Elem<E> p = head.next;
        
        for ( int i=0; i<pos; i++ ) {
            p = p.next;
        }

        return p.value;
    }

    public void add( E obj ) {

        if ( obj == null ) {
            throw new IllegalArgumentException( "null" );
        }

        size++;

	Elem<E> before, after;

	before = head.previous;
	after = head;

	before.next = new Elem<E>( obj, before, after );
	after.previous = before.next;
    }

    public void remove( int pos ) {

        if ( pos < 0 || pos > (size-1) ) {
            throw new IndexOutOfBoundsException( Integer.toString( pos ) );
        }

        Elem<E> left = head; // starts at head, not head.next!
        
        for ( int i=0; i < pos; i++ ) {
            left = left.next;
        }

        Elem<E> current = left.next;
        Elem<E> right = current.next;

        left.next = right;
        right.previous = left;

        size--;
    }
}