/**
  * Lista doppiamente concatenata: classe didattica
  * @author A. Luchetta
  * @version 20-Nov-2006
  * @see EmptyLinkedListException
*/
public class DoublyLinkedList implements Container
{
   // parte privata
   private ListNode head, tail;
   private int size;

   /**
      costruttore
   */
   public DoublyLinkedList()
   {
      makeEmpty();
   }

   /**
      rende la lista vuota
   */
   public void makeEmpty()
   {
      head = new ListNode();
      tail = new ListNode();
      head.setNext(tail);
      tail.setPrevious(head);
      size = 0;
   }

   /**
      verifica se la lista e' vuota
      @return true se la lista e' vuota, false altrimenti
   */
   public boolean isEmpty()
   {
      return head.getNext() == tail;
   }
   
   /**
      @return numero di elementi nella lista
      @throws EmptyLinkedListException se la lista e' vuota
   */
   public int size()
   {
      return size;
   }
   /**
      ispeziona il primo elemento della lista
      complessita' temporale O(1)
      @return il primo elemento della lista
   */
   public Object getFirst() throws EmptyLinkedListException
   {
      if (isEmpty())
         throw new EmptyLinkedListException();

      return head.getNext().getElement();
   }

    /**
      ispeziona l'ultimo elemento della lista
      complessita' temporale O(1)
      @return l'ultimo elemento della lista
   */
   public Object getLast() throws EmptyLinkedListException
   {
      if (isEmpty())
         throw new EmptyLinkedListException();

      return tail.getPrevious().getElement();
   }

    /**
      inserisce un elemento in testa alla lista
      complessita' temporale O(1)
      @param e l'elemento da inserire
   */
   public void addFirst(Object e)
   {
      // inserisce il dato nell’header attuale
      head.setElement(e);

      // crea un nodo con tre riferimenti null
      ListNode newNode = new ListNode();

      // collega il nuovo nodo all’header attuale
      newNode.setNext(head);

      // il nuovo nodo diventa il nodo header
      head = newNode;
      
      // incremento del numero di elementi
      size++;

      // tail non viene modificato
   }

    /**
      rimuove un elemento in testa alla lista
      complessita' temporale O(1)
      @return l'elemento rimosso
   */
   public Object removeFirst() throws EmptyLinkedListException
   {
      // delega a getFirst il controllo di lista vuota
      Object e = getFirst();

      // aggiorno l’header
      head = head.getNext();

      // cancello l'elemento nel header
      head.setElement(null);
      
      // decremento del numero di elementi
      size--;

      return e;
   }

    /**
      inserisce un elemento in coda alla lista
      complessita' temporale O(1)
      @param e l'elemento da inserire
   */
   public void addLast(Object e)
   {
      // inserisco l'elemento nel nodo tail
      tail.setElement(e);
      
      /* costruisco un nuovo nodo che non contiene elementi, non ha un nodo
         successivo e ha come nodo precedente il nodo tail
      */
      ListNode newNode = new ListNode(null, null, tail);
 
      // il nodo successivo a tail diventa il nuovo nodo
      tail.setNext(newNode);

      // il nuovo tail diventa il nuovo nodo
      tail = newNode;
      
      // incremento del numero di elementi
      size++;
   }

    /**
      rimuove un elemento in coda alla lista
      complessita' temporale O(1)
      @return l'elemento rimosso
   */
   public Object removeLast() throws EmptyLinkedListException
   {
      // delega a getLast il controllo di lista vuota
      Object e = getLast();

      // nodo precedente al nodo contenente l'ultimo elemento
      tail.getPrevious().setElement(null);

      // il prossimo nodo diventa tail
      tail = tail.getPrevious();

      // decremento del numero di elementi
      size--;

      return e;
   }

   class ListNode
   {
      private Object element;
      private ListNode next;
      private ListNode previous;
 
      public ListNode(Object e, ListNode n, ListNode p)
      {
        element = e;
        next = n;
        previous = p;
      }
 
      public ListNode()
      {
         this(null, null, null);
      }
 
      public Object getElement() { return element; }
 
      public ListNode getNext()  { return next; }
      
      public ListNode getPrevious()  { return previous; }
 
      public void setElement(Object e) { element = e; }
 
      public void setNext(ListNode n) {  next = n; }

      public void setPrevious(ListNode p) {  previous = p; }
   }
}