public class LinkedList<E> {
  private Node<E> head, tail;
  
  public LinkedList() {
    head = new Node<>(null, null, null);
    tail = new Node<>(null, head, null);
    head.setNext(tail);
  }
  
  private class Node<E> {
    private Node<E> next, prev;
    private E e;
  
    public Node(Node<E> nxt, Node<E> prv, E elem) {
      next = nxt;
      prev = prv;
      e = elem;
    }
    
    public Node<E> getNext() {return next;}
    public void setNext(Node<E> nxt) { next = nxt; }
    public Node<E> getPrev() {return prev;}
    public void setPrev(Node<E> prv) { prev = prv; }
    public E getElement() { return e; }
    public void setElement(E elem) { e = elem; }
  }
  
  private class Iterator<E> implements java.util.Iterator {
    Node<E> curr;
    public Iterator(Node<E> c) {
      curr = c;
    }
    public boolean hasNext() {
      if(curr.getNext() != tail)
        return true;
      return false;
    }
    public E next() {
      curr = curr.getNext();
      return curr.getElement();
    }
    public void remove() {
      curr.getPrev().setNext(curr.getNext());
      curr.getNext().setPrev(curr.getPrev());
      curr = null;
    }
  }
  
  Iterator<E> iterator() {
    return new Iterator<E>(head);
  }
  
  // append in the end
  public void add(E elem) {
    Node<E> plus = new Node<E>(tail, tail.getPrev(), elem);
    tail.getPrev().setNext(plus);
    tail.setPrev(plus);
  }
  
  public boolean contains(E elem) {
    Iterator<E> it = iterator();
    while(it.hasNext()) {
      E e = it.next();
      if( e.equals(elem) )
        return true;
    }
    return false;
  }
  
  public int indexOf(E elem) {
    Iterator<E> it = iterator();
    int index = -1;
    while(it.hasNext()) {
      E e = it.next();
      index++;
      if( e.equals(elem) )
        return index;
    }
    return -1;
  }
}