// A reference-based indexed list.

public class IndexedList extends SimpleList
{
	
	public void add( int index, Object element ) throws IndexOutOfBoundsException
	{
    	if ( index >= 1 && index <= numelements + 1 ) 
    	{
       		if ( index == 1 ) 
       		{
           		// insert the new node containing element at beginning of list
           		Node newNode = new Node( element, head );
           		head = newNode;
       		} 
       		else 
       		{
           		Node prev = find( index-1 );
           		// insert the new node containing element after the node that prev references 
           		Node newNode = new Node( element, prev.getNext( ) );
           		prev.setNext( newNode );
       		} // end if
       		numelements++;
    	} 
    	else
    	{  
       		throw new IndexOutOfBoundsException("List index out of bounds exception on add");
    	}
	}  // end add


	public void remove( int index ) throws IndexOutOfBoundsException 
	{
    	if (index >= 1 && index <= numelements) 
    	{
       		if (index == 1) 
       		{
          		// delete the first node from the list
          		head = head.getNext();
       		} 
       		else
      		{
        		Node prev = find(index-1);
        	  	// delete the node after the node that prev references, save reference to node
        	  	Node curr = prev.getNext(); 
        	  	prev.setNext(curr.getNext());
       		} // end if
       	numelements--;
    	} // end if
    	else 
    	{
    	    throw new IndexOutOfBoundsException( "List index out of bounds exception on remove");
    	} // end if
	}	   	// end remove


	private Node find(int index) 
	{
	   // --------------------------------------------------
	   // Locates a specified node in a linked list.
	   // Precondition: index is the number of the desired
	   // node. Assumes that 1 <= index <= numelements+1 
	   // Postcondition: Returns a reference to the desired 
	   // node.
	   // -------------------------------------------------- 
	   Node curr = head;
	   for (int skip = 1; skip < index; skip++) 
	   {
	      curr = curr.getNext();
	    } // end for
	    return curr;
	} // end find
	
	
	public static void main( String args[ ] )
 	{
   		System.out.println( "-----------------------\nCreating a list...");
   		IndexedList myList = new IndexedList( );
   		
		System.out.println( "Adding some elements...\n"); 
   		myList.addToFront( new Integer( 4 ) );
   		myList.addToFront( new Integer( 2 ) );
   		myList.addToFront( new Integer( 1 ) );
   		
   		System.out.println( "Current List:");
   		myList.printList();
   		System.out.print("\n");
   
   		System.out.println("Adding a 3...");
   		myList.add(3, new Integer(3));
   		myList.printList();
   		System.out.print("\n");
   		
   	   	System.out.println("Adding a 10...");
   		myList.add(2, new Integer(10));
   		myList.printList();
   		System.out.print("\n");
   		
   		System.out.println("Removing the 10...");
   		myList.remove(2);
   		myList.printList();
   		System.out.print("\n");	   		
   		System.out.println( "-----------------------");
 	}
	
	
}