/* A linked list with sentinels at head and tail.
 */
public class LinkedList<E> {
  private Node<E> head, tail;
  int size;
  
  public LinkedList() {
    head = new Node<>(null, null, null);
    tail = new Node<>(null, head, null);
    head.setNext(tail);
    size = 0;
  }
  
  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<E> {
    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 = curr.getPrev();
    }
  }
  
  Iterator<E> iterator() {
    return new Iterator<E>(head);
  }
  
  // append in the end
  public boolean add(E elem) {
    Node<E> plus = new Node<E>(tail, tail.getPrev(), elem);
    tail.getPrev().setNext(plus);
    tail.setPrev(plus);
    size++;
    return true;
  }
  
  public boolean add(int index, E elem) {
    if(index>size)
      return false;
    Node<E> curr = head.next;
    for(int i=0; curr != tail && i<index; i++) {
      curr = curr.next;
    }
    Node<E> plus = new Node<E>(curr, curr.prev, elem);
    curr.prev.next = plus;
    curr.prev = plus;
    size++;
    return true;
  }
  
  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;
  }
  
  int size() {
    return size;
  }
}