public class LinkedList
{
   //********  Defining & Accessing State
   private Node first;  //Reference to the 1st element
   
   //Constructor
   public LinkedList()
   {
      this.first = null;
   }
   
   //Answer if the list is empty
   public boolean isEmpty()
   {
      return this.first == null;
   }
   
   //Return the number of elements (stored items) 
   public int size()
   {
      int counter = 0;
      
      Node pointer = this.first;
      while (pointer != null)
      {
         counter = counter + 1;
         pointer = pointer.next;
      }
      
      return counter;
   }
   
   //Search: Answer if a given item is stored   
   public boolean contains(Object item)
   {
      Node pointer = this.first;
      while (pointer != null)
      {
         if (pointer.data.equals(item))
            return true;
         
         pointer = pointer.next;
      }
            
      return false;
   }
   
   //********  Operations at the HEAD of the linked list
   //Add an item at the head of the list
   public void addFirst(Object item)
   {
      Node store = new Node(item);
      
      store.next = this.first;
       
      this.first = store;
   }

   //Remove and return the item from the head of the list
   public Object removeFirst()
   {
      if (this.first == null)
         return null;
         
      Object item = this.first.data;
      
      this.first = this.first.next;
      
      return item;
   }
   
   //********  Operations at the TAIL of the linked list
   //Add an item at the tail of the list
   public void addLast(Object item)
   {
      Node store = new Node(item);
      
      if (this.first == null)
         this.first = store;
      else
      {      
         Node pointer = this.first;
         while (pointer.next != null)
            pointer = pointer.next;
         
         pointer.next = store;
      }
   }

   //Remove and return the item from the tail of the list
   public Object removeLast()
   {
      if (this.first == null)
         return null;
   
      Node pointer = this.first;
      Node trailer = null;
      while (pointer.next != null)
      {
         trailer = pointer;
         pointer = pointer.next;
      }
      
      if (pointer == this.first) //trailer == null
         this.first = null;
      else
         trailer.next = null;
         
      return pointer.data;
   }
    
   //********  Generalized Operations on a linked list
   //Search and Remove a given item from the list
   public boolean remove(Object item)
   {
      Node pointer = this.first;
      Node trailer = null;
      
      while(pointer != null && !pointer.data.equals(item)) 
      {
         trailer = pointer;
         pointer = pointer.next;
      }
      
      if (pointer == null)
         return false;
         
      if (trailer == null) //first element
         this.first = pointer.next;
      else
         trailer.next = pointer.next;
         
      return true;
   }
   
   //Add an item adjacent to a specified existing element.
   //@param item  : The item to be added to the list
   //@param mark  : An existing item in the list
   //@param before: Desired position of item relative to mark
   //               true : before mark    false: after mark
   public void insert(Object item, Object mark, boolean before)
   {
      Node pointer = this.first;
      Node trailer = null;
      
      while (pointer != null & !pointer.data.equals(mark))
      {
         trailer = pointer;
         pointer = pointer.next;
      }
      
      if (pointer == null) //The mark was not located
         if (before)
            this.addFirst(item);
         else
            this.addLast(item);
      else                 //Add adjacent to the mark data
      {
         Node store = new Node(item);
         if (before)
         {
            store.next = pointer;
            if (trailer == null)
               this.first = store;
            else
               trailer.next = store;
         }
         else
         {
            store.next = pointer.next;
            pointer.next = store;
         }
      }
   }
      
   //********  Representation of an Element (Storage Node)   
   private class Node
   {
      Object data;
      Node next;
      public Node(Object item)
      {
         this.data = item;
         this.next = null;
      }
   }
}