class MyLinkedList
{
   //erstes Element in der Liste
   public MyListElement head;
   //letztes Element in der Liste
   public MyListElement tail;  
   //Anzahl der Elemente in der Liste
   public int numberOfElements;

   //Methode zum Einfuegen eines Elements am Ende der Liste
   public void addElementAtTail(int x)
   {
      //neues Listenelement anlegen
      MyListElement newListElement = new MyListElement();
      //die in diesem Listenelement zu speichernde Zahl ablegen
      newListElement.z = x;
      //die Verbindung zur bisherigen verketteten Liste herstellen
      if(numberOfElements == 0)
      {
         head = newListElement;
         tail = newListElement;
      }
      else
      {
         newListElement.prev = tail;
         tail.next = newListElement;
         tail = newListElement;
      }

      numberOfElements++;
   }

   //Konstruktor der Klasse
   public MyLinkedList()
   {
      numberOfElements = 0;
   }

   //Methode zur Ausgabe aller Elemente in der Liste
   public void printAllElements()
   {
      //Ausgabe soll mit dem ersten Element starten
      MyListElement e = head;

      //Schleife zum Durchlaufen der Liste
      for(int i = 0; i < numberOfElements; i++)
      {
         //Ausgabe der im Element e abgelegten Zahl
         System.out.println(e.z);
         //gehe zum naechsten Element
         e = e.next;
      }
   }

   //Methode zum Einfuegen eines Elements am Beginn der Liste
   public void addElementAtHead(int x)
   {
      //neues Listenelement anlegen
      MyListElement newListElement = new MyListElement();
      //die in diesem Listenelement zu speichernde Zahl ablegen
      newListElement.z = x;
      //die Verbindung zur bisherigen verketteten Liste herstellen
      if(numberOfElements == 0)
      {
         head = newListElement;
         tail = newListElement;
      }
      else
      {
         newListElement.next = head;
         head.prev = newListElement;
         head = newListElement;
      }

      numberOfElements++;
   }

   //Methode zum Entfernen des letzten Elements in der Liste
   public int removeLastElement()
   {
      //Wir wollen uns die im zu entfernenden
      //Listenelement abgelegte Zahl merken.
      int x = 0;
      //Nur wenn die Liste mindestens ein Element enthaelt,
      //gibt es tatsaechlich etwas zu entfernen.
      if(numberOfElements > 0)
      {
         //abgelegte Zahl merken
         x = tail.z;
         //tail aktualisieren
         tail = tail.prev;
         //Anzahl der Elemente aktualisieren
         numberOfElements--;
         //Wenn noch Elemente uebrig sind, soll
         //das letzte keinen Nachfolger haben.
         if(numberOfElements > 0)
         {
            tail.next = null;
         }
      }
      
      return x;
   }

   //Methode zum Entfernen des ersten Elements in der Liste
   public int removeFirstElement()
   {
      //Wir wollen uns die im zu entfernenden
      //Listenelement abgelegte Zahl merken.
      int x = 0;
      //nur wenn die Liste mindestens ein Element enthaelt,
      //gibt es tatsaechlich etwas zu entfernen
      if(numberOfElements > 0)
      {
         x = head.z;
         //head aktualisieren
         head = head.next;
         //Anzahl der Elemente aktualisieren
         numberOfElements--;
         //Wenn noch Elemente uebrig sind, soll
         //das erste keinen Vorgaenger haben.
         if(numberOfElements > 0)
         {
            head.prev = null;
         }
      }
      
      return x;
   }
}