//Customized linked list implementation
public class MyLinkedList
{
   //Instance Variable
	private Node first;
	
   //Default Constructor: Create an empty list
	public MyLinkedList()
	{
		this.first = null;
	}

   //Accessor: Return true if this list is empty, otherwise false
	public boolean isEmpty()
	{
		return this.first == null;
	}
	
   //Mutator: Add a new item first (at the head) in this list
	public void addFirst(Object item)
	{
		Node store = new Node(item);
		store.next = this.first;
		this.first = store;
	}
	
   //Mutator: Remove and return the first item from this list
	public Object removeFirst()
	{
		if (this.first == null)
			return null;
			
		Object item = this.first.data;
		this.first = this.first.next;
		
		return item;
	}
	
   //Return the size (# of elements) of this list
	public int size()
	{
		int count = 0;
		
		Node pointer = this.first;
		while (pointer != null)
		{
			count++;
			pointer = pointer.next;
		}
		
		return count;
	}
	
   //Answer true if any element of this list matches parameter item
	public boolean contains(Object item)
	{
		Node pointer = this.first;
		while (pointer != null && !pointer.data.equals(item))
			pointer = pointer.next;
			
		return pointer != null ;
	} 

   //Mutator: Add a new item last (at the tail) in this list
	public void addLast(Object item)
	{
		Node store = new Node(item);
		
		Node pointer = this.first;
		Node trailer = null;
		
      //Set trailer to locate the last node
		while (pointer != null)
		{
			trailer = pointer;
			pointer = pointer.next;
		}
		
		if (trailer == null) //list is empty
			this.first = store;
		else
			trailer.next = store;
	}

   //Mutator: Remove and return the last item of this list
  	public Object removeLast()
   {
		if (this.first == null) //list is empty
			return null;
		
      //Set pointer to locate the last node
      //Set trailer to locate the penultimate node	
		Node pointer = this.first;
		Node trailer = null;
		while (pointer.next != null)
		{
			trailer = pointer;
			pointer = pointer.next;
		}
		
		if (trailer == null) //removing ONLY node
			this.first = null;
		else
			trailer.next = null;
			
		return pointer.data;
   }
   
   //Mutator: Add a new item into this list, placing it immediately
   // following the item referenced by marker
	public void addAfter(Object marker, Object newItem)
	{
		Node pointer = this.first;
		while (pointer != null && !pointer.data.equals(marker) )
			pointer = pointer.next;
			
		if (pointer == null)
			this.addFirst(newItem);
		else
		{
			Node store = new Node(newItem);
			store.next = pointer.next;
			pointer.next = store;
		}
	}
	
   //Mutator: Add a new item into this list, placing it immediately
   // before the item referenced by marker
	public void addBefore(Object marker, Object newItem)
	{
		Node pointer = this.first;
		Node trailer = null;
		while (pointer != null && !pointer.data.equals(marker) )
		{
			trailer = pointer;
			pointer = pointer.next;
		}
		
		if (pointer == null)
			this.addFirst(newItem);
		else
		{
			Node store = new Node(newItem);
			store.next = pointer;
			if (trailer == null)
				this.first = store;
			else
				trailer.next = store;
		}
	}
   
   //Mutator: Search for and remove an item from this list that
   // matches the parameter item
	public void remove(Object item)
	{
		Node pointer = this.first;
		Node trailer = null;
      
      //Set pointer to locate a node with matching data
      //Set trailer to locate the preceding node
		while (pointer != null && !pointer.data.equals(item))
		{
			trailer = pointer;
			pointer = pointer.next;
		}
		
		if (pointer != null)    //Found a matching item
			if (trailer == null) //pointer == this.first
				this.first = pointer.next;
			else
				trailer.next = pointer.next;
	}
	
	public String toString()
	{
		String image = this.size() + " Items";
		
		Node pointer = this.first;
		while (pointer != null)
		{
			image += "\n" + pointer.data;
			pointer = pointer.next;
		}
			
		return image;
	}	
   
   //Inner class 
   //Representation of a storage element of this list
	private class Node
	{
		public Object data;
		public Node next;
		
		public Node(Object item)
		{
			this.data = item;
			this.next = null;
		}
	}
}