/** A class to represent a single-linked list with 
a link from each node to the next node */
public class SingleLinkedList<E> 
{

  //reference to list head 
  private Node<E> head = null; 
  //------------------------------------------

  /** Insert a node to the beginning of the list.
      @param item - the item to be added
  */
  public void addFirst(E item) {
    head = new Node<E>(item,head);
  }
  //------------------------------------------
  
  /** Insert node in list after node referenced to by p
      @param p - the node to insert after
		@param data - data to store in the new node
  */
  public void insertNode(Node<E> p, E data)
  {
    Node<E> newNode = new Node<E>(data);
	 newNode.next = p.next;
	 p.next = newNode;
  }
  //------------------------------------------

   /** Delete the node after the node referenced to by p
      @param p - the node to delete the node after
		@return reference to the removed node
  */
  public Node<E> removeNode(Node<E> p)
  {
    Node<E> deletedNode = p.next;
    p.next = p.next.next;
	 return deletedNode;
  }//end removeNode()
  //------------------------------------------


   
  /** This method traverses and returns a string 
      representation of the lis. Element values are 
		separated by ==> in  the string representation */
  public String toString()
  {
    Node<E> p = head;
	 StringBuilder sb = new StringBuilder();
	 
	 while (p != null)
	 {
	   sb.append(p.data);
		if (p.next != null)
		  sb.append(" ==> ");
		p = p.next;
	 }

    return sb.toString();
  }//end toString()
  //------------------------------------------

  //########################################
  /** A Node is the building block for linked lists. */
  private static class Node < E > 
  {
   private E data; // The data value
   private Node<E> next; // The link to the next node 

   /** Construct a new node with the given data value.
       @param dataItem The data value */
   private Node(E dataItem) 
	{ 
	  data = dataItem; 
	  next = null; 
	}

   /** Construct a new node that references another node.          
   @param dataItem The data value
       @param nodeRef The node referenced by new node */
    private Node(E dataItem, Node < E > nodeRef ) { 
     data = dataItem; 
     next = nodeRef; }
  } //end inner class Node
    //########################################

}//end class SingleLinkedList