class ListNode {
  Object item;
  ListNode next;
}

class List {
  /** Construct an empty list */
  public List() {
    size = 0;
    head = null;
  }

  /** Construct a list that is a copy of L  */
  public List (List L) {
    size = L.size;
    if (L.head == null) {
      head = null;
    }
    else {
      head = new ListNode();
      /* check that there was enough space    */
      head.item = L.head.item;
	
      /* Now copy the rest of the List.      */
      /* First, make a pointer into the list */
      ListNode newPrev = head; 
      for (ListNode origCur = L.head.next;
	   origCur != null;
	   origCur = origCur.next) {
	/* put a new (unitialized) node on the end */
	newPrev.next = new ListNode();
	/* check that there was enough space */
	newPrev = newPrev.next;
	/* fill in the item in the current node */
	newPrev.item = origCur.item;
      }
      newPrev.next = null;
    }
  }

  /** Postcondition: Return true if this list is empty, */
  /**  false otherwise.                                 */
  public boolean isEmpty() {
    return (size == 0);
  }

    
  /** Postcondition: Return the length of this list. */
  public int length() {
    return size;
  }

  /** Postcondition: If this list has at least newPosition-1   */
  /**  elements, newItem will be inserted after newPosition-1, */
  /**  making it the element at newPosition, and true will     */
  /**  returned.  If list has less than newPosition-1 elements */
  /**  or newPosition is less than 1, the list will be left    */
  /**  unchanged and success will be false.                    */
  /**  (Positions in a list start at 1, not 0.)                */
  public boolean insert (int newPosition, Object newItem) {
    int newLength = length() + 1;
    boolean success = ((newPosition >= 1) && 
		      (newPosition <= newLength));
    if (success) {
      size = newLength;
      /* create a new node and place newItem in it */
      ListNode newPtr = new ListNode();
	      
      newPtr.item = newItem;
      if (newPosition == 1) {
	/* insert new node at the beginning */
	newPtr.next = head;
	head = newPtr;
      }
      else {
	ListNode prev = ptrTo (newPosition-1);
	/* insert new node after node */
	newPtr.next = prev.next;
	prev.next = newPtr;
      }
    }
    return success;
  }
    	
  /** Postcondition: If position < 1 or position > length(), */
  /**   then null is returned.  Otherwise, the item at       */
  /**   position is returned.  The list is unchanged in      */
  /**   either case.                                         */
  public Object retrieve(int position) {
    if ((position >= 1) && (position <= length())) {
      // get pointer to the node, the data in node
      ListNode cur = ptrTo(position);
      return (cur.item);
    }
    else {
      return null;
    }
  } 
    
  /** Postcondition: If this list has at least position      */
  /**  elements, the item at position will be deleted from   */
  /**  the list and true will be returned.  If list          */
  /** has less than position elements, the list will be      */
  /** left unchanged and false will be returned.             */
  public boolean remove (int position) {
    ListNode cur = null;
    boolean success = ((position >= 1) && 
		       (position <= length()));
        
    if (success) {
      size = size -1;
      /* Unlink the node using 2 cases: it is  */
      /* either the first node or not          */
      /* Make cur point to the unlinked node   */
      if (position == 1) {
	cur = head;
	head = head.next;
      }
      else {
	ListNode prev = ptrTo (position -1);
	/** Remove the node after the node to  */
    	/** which prev points */
    	cur = prev.next;
    	prev.next = cur.next;
      }
      /** return node to the system */
      cur.next = null;  
      cur = null;	   
    }
    return success;
  }
    
  /** Postcondition: Add newItem to the end of the list.     */
  public void addToEnd (Object item) {
  }
    
  /** Postcondition: If item is in the list, returns true    */
  /**   otherwise returns false.  This method is looking for */
  /**   the object item, not a copy of it.                   */
  /** Performance: this operation should work in linear time.*/
  public boolean isIn (Object item) {
    /* replace the following line with your code */
    return false;
  }
    
  /** Postcondition:  Returns a pointer to the node at     */
  /**      position.  If position < 1 or position > the    */
  /**      size of the list, returns null.                 */
  private ListNode ptrTo (int position) {
    if (( position < 1) || (position > length())) {
      return null;
    }
    else {
      // count from the beginning of the list
      ListNode trav = head;
      for (int Skip = 1; Skip < position; Skip++) {
	trav = trav.next;
      }
      return trav;
    }
  }
    
  public String toString() {
    int i;
    Object item;
    String result = "[  ";
    for (i = 1; i <= this.length(); i++) {
	item = (Integer) this.retrieve(i);
	result = result + item.toString() + "  ";
    }
    result = result + "]";
    return result;
  }

  private int size;
    
  private ListNode head;
}

    
class Test {    
  public static void main (String[] argv) {
    List l1 = new List();  // an empty list is not the same as null
    boolean success;
    success = l1.insert(1,new Integer(3));
    success = l1.insert(1,new Integer(2));
    success = l1.insert(1,new Integer(1));
    success = l1.insert(4,new Integer(4));

    System.out.print("Here is l1 after 4 inserts: ");
    System.out.println(l1.toString());;

    System.out.println("\nPart 1 outputs are here");

    System.out.println("\nPart 2 outputs are here");

    System.out.println("\nPart 3 outputs are here");
  }

}