
class LinkedList {
  private LinkedListNode first, last;
  private int size;
  
  public LinkedList() {
    clear();
  }

  public LinkedList( LinkedList other ) {
    this();

    addAll( other );
  }

  public void add( Object obj ) {
    addLast( obj );
  }

  public void addFirst( Object obj ) {
    LinkedListNode node = new LinkedListNode( obj, first, first.getNext() );
    first.getNext().setPrev( node );
    first.setNext( node );

    size++;
  }

  public void addLast( Object obj ) {
    LinkedListNode node = new LinkedListNode( obj, last.getPrev(), last );
    last.getPrev().setNext( node );
    last.setPrev( node );

    size++;
  }

  public void addAll( LinkedList other ) {
    for ( LinkedListNode node=other.first.getNext(); node!=other.last; node=node.getNext() )
      add( node.getValue() );
  }

  public Object get( int index ) {
    checkIndex( index );

    return findNode( index ).getValue();
  }
  
  public Object set( int index, Object obj ) {
    checkIndex( index );

    LinkedListNode node = findNode( index );
    Object oldValue = node.getValue();
    node.setValue( obj );

    return oldValue;
  }

  public void add( int index, Object obj ) {
    if ( index == size )
      addLast( obj );

    else {
      checkIndex( index );

      LinkedListNode node = findNode( index );

      LinkedListNode newNode = new LinkedListNode( obj, node.getPrev(), node );
      newNode.getPrev().setNext( newNode );
      newNode.getNext().setPrev( newNode );
      size++;
    }
  }
  
  public Object getFirst() {
    if ( size > 0 )
      return first.getNext().getValue();
    else
      return null; // todo - should throw NoSuchElementException
  }
  
  public Object getLast() {
    if ( size > 0 )
      return last.getPrev().getValue();
    else
      return null; // todo - should throw NoSuchElementException
  }

  public Object remove( int index ) {
    checkIndex( index );

    LinkedListNode node = findNode( index );
    removeNode( node );
    return node.getValue();
  }
  
  public boolean remove( Object obj ) {
    LinkedListNode node = findNode( obj );

    if ( node != null ) {
      removeNode( node );

      return true;
    } else
      return false;
  }
  
  public Object removeFirst() {
    if ( size > 0 ) {
      LinkedListNode node = first.getNext();
      removeNode( node );
      return node.getValue();

    } else
      return null; // todo - should throw NoSuchElementException
  }
  
  public Object removeLast() {
    if ( size > 0 ) {
      LinkedListNode node = last.getPrev();
      removeNode( node );
      return node.getValue();

    } else
      return null; // todo - should throw NoSuchElementException
  }

  private void removeNode( LinkedListNode node ) {
    node.getPrev().setNext( node.getNext() );
    node.getNext().setPrev( node.getPrev() );
    size--;
  }

  public void clear() {
    first = new LinkedListNode( null );
    last = new LinkedListNode( null );

    first.setNext( last );
    last.setPrev( first );

    size = 0;
  }
  
  public int size() {
    return size;
  }
  
  public boolean isEmpty() {
    return size == 0;
  }
  
  public boolean contains( Object obj ) {
    return indexOf( obj ) >= 0;
  }

  public int indexOf( Object obj ) {
    int index = 0;

    for ( LinkedListNode node=first.getNext(); node!=last; node=node.getNext() ) {
      Object value = node.getValue();

      if ( obj == null && value == null || obj != null && obj.equals( value ) )
        return index;

      index++;
    }

    return -1;
  }

  public int lastIndexOf( Object obj ) {
    int index = size - 1;

    for ( LinkedListNode node=last.getPrev(); node!=first; node=node.getPrev() ) {
      Object value = node.getValue();

      if ( obj == null && value == null || obj != null && obj.equals( value ) )
        return index;

      index--;
    }

    return -1;
  }

  public Object[] toArray() {
    Object[] result = new Object[ size ];
    int index = 0;

    for ( LinkedListNode node=first.getNext(); node!=last; node=node.getNext() ) {
      result[ index ] = node.getValue();

      index++;
    }    

    return result;
  }

  private void checkIndex( int index ) {
    if ( index < 0 || index >= size )
      throwRuntimeError( "IndexOutOfBoundsException", "index", "" + index );
  }

  private LinkedListNode findNode( int index ) {
    int current = 0;

    for ( LinkedListNode node=first.getNext(); node!=last; node=node.getNext() ) {
      if ( current == index )
        return node;

      current++;
    }

    return null;
  }
  
  private LinkedListNode findNode( Object obj ) {
    for ( LinkedListNode node=first.getNext(); node!=last; node=node.getNext() ) {
      Object value = node.getValue();

      if ( obj == null && value == null || obj != null && obj.equals( value ) )
        return node;
    }

    return null;
  }
  
  public String toString() {
    String result = "[LinkedList:";

    if ( size > 0 )
      for ( LinkedListNode node=first.getNext(); node!=last; node=node.getNext() ) {
        result += " " + node.getValue();

        if ( node != last.getPrev() )
          result += ",";
      }
    else
      result += " empty";

    result += "]";

    return result;
  }
}

class LinkedListNode {
  private Object value;
  private LinkedListNode prev, next;

  public LinkedListNode( Object value ) {
    this( value, null, null );
  }

  public LinkedListNode( Object value, LinkedListNode prev, LinkedListNode next ) {
    this.value = value;
    this.prev = prev;
    this.next = next;
  }

  public Object getValue() {
    return value;
  }

  public void setValue( Object value ) {
    this.value = value;
  }

  public LinkedListNode getPrev() {
    return prev;
  }

  public void setPrev( LinkedListNode prev ) {
    this.prev = prev;
  }

  public LinkedListNode getNext() {
    return next;
  }

  public void setNext( LinkedListNode next ) {
    this.next = next;
  }
}
