import java.util.Iterator;
import java.util.ConcurrentModificationException;

class MyLinkedList<AnyType> implements Iterable<AnyType>
{
    public MyLinkedList( )
    {
        header = new Node<AnyType>( null, null, null );
        tail   = new Node<AnyType>( null, header, null );
        header.next = tail;
        theSize = 0;
    }

    private static class Node<AnyType>
    {
        AnyType data;
        Node<AnyType> prev;
        Node<AnyType> next;

        Node( AnyType d, Node<AnyType> p, Node<AnyType> n )
        {
            data = d;
            prev = p;
            next = n;
        }
    }

    private class MyIterator implements Iterator<AnyType>
    {
        public boolean hasNext( )
        {
            checkForModification( );
            return current != tail;
        }

        public AnyType next( )
        {
            checkForModification( );
            if( !hasNext( ) )
                throw new IllegalStateException( "Iterator out of bounds" );

            AnyType nextData = current.data;
            current = current.next;
            okToRemove = true;
            return nextData;
        }

        public void remove( )
        {
            checkForModification( );
            if( !okToRemove )
                throw new IllegalStateException( "Illegal remove" );

            okToRemove = false;
            theExpectedModCount++;
            removeNode( current.prev );
        }

        private void checkForModification( )
        {
            if( modCount != theExpectedModCount )
                throw new ConcurrentModificationException( );
        }

        private Node<AnyType> current = header.next;
        private boolean okToRemove = false;
        private int theExpectedModCount = modCount;
    }


    public void addFirst( AnyType x )
    {
        addBefore( x, header.next );
    }

    public void addLast( AnyType x )
    {
        addBefore( x, tail );
    }

    private void addBefore( AnyType x, Node<AnyType> p )
    {
        p.prev = p.prev.next = new Node<AnyType>( x, p.prev, p );

        theSize++;
        modCount++;
    }

    public boolean contains( AnyType x )
    {
        for( Node<AnyType> p = header.next; p != tail; p = p.next )
            if( p.data.equals( x ) )
                return true;

        return false;
    }

    public void removeFirst( )
    {
        if( isEmpty( ) )
            throw new IllegalStateException( "Empty list" );

        removeNode( header.next );
    }

    public void removeLast( )
    {
        if( isEmpty( ) )
            throw new IllegalStateException( "Empty list" );

        removeNode( tail.prev );
    }

    private void removeNode( Node<AnyType> p )
    {
        p.prev.next = p.next;
        p.next.prev = p.prev;
        theSize--;
        modCount++;
    }

    public String toString( )
    {
        StringBuffer sb = new StringBuffer( "[ ");

        for( Node<AnyType> p = header.next; p != tail; p = p.next )
            sb.append( p.data + " " );

        sb.append( "]" );
        return new String( sb );
    }

    public int size( )
    {
        return theSize;
    }

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

    public Iterator<AnyType> iterator( )
    {
        return new MyIterator( );
    }

    private Node<AnyType> header;
    private Node<AnyType> tail;
    private int theSize;
    private int modCount; // number of modifications
}


class Day11
{
    public static void removeEvens( MyLinkedList<Integer> lst )
    {
        Iterator<Integer> itr = lst.iterator( );

        while( itr.hasNext( ) )
        {
            if( itr.next( ) % 2 == 0 )
                itr.remove( );
        }
    }

    public static void main( String [ ] args )
    {
        MyLinkedList<Integer> lst = new MyLinkedList<Integer>( );

        for( int i = 0; i < 10; i++ )
        {
            lst.addFirst( i );
            lst.addLast( 4 - i );
        }

        System.out.println( lst );

        removeEvens( lst );
        System.out.println( lst );

        System.out.println( "Size is: " + lst.size( ) );

        lst.removeFirst( );  // remove item at index 0
        lst.addLast( 1000 );
        Iterator<Integer> itr = lst.iterator( );
        System.out.println( lst );
        System.out.println( "First item is: " + itr.next( ) );
        
    }
}