// *********************************************
// Reference-based implementation of ADT list.
// *********************************************
public class ListReferenceBased implements ListInterface
{
    // reference to linked list of items
    private Node head;

    // definitions of constructors and methods
    public ListReferenceBased()
    {
        head = null;
    } // end default constructor

    public boolean isEmpty()
    {
    } // end isEmpty

    public int size()
    {
    } // end size

    public Node find(int index)
    {
        // --------------------------------------
        // Locates a specified node in a linked list.
        // Precondition: index is the number of the desired
        // Postcondition: Returns a reference to the desired node.
        // --------------------------------------------------------
        Node curr = head;
        for (int skip = 0; skip < index; skip++)
        {
            curr = curr.next;
        } // end for
        return curr;
    } // end find

    public Comparable get(int index) throws ListIndexOutOfBoundsException
    {
        if (index >= 0)
        {
            // get reference to node, then data in node
            Node curr = find(index);
            Comparable dataItem = curr.item;
            return dataItem;
        }
        else
        {
            throw new ListIndexOutOfBoundsException("List index out of bounds on get");
        } // end if
    } // end get

    public void add(int index, Comparable item) throws ListIndexOutOfBoundsException
    {
        if (index >= 0)
        {
            if (index == 0)
            {
                // insert the new node containing item at beginning of list
                Node newNode = new node(item, head);
                head = newNode;
            }
            else
            {
                Node prev = find(index-1);

                // insert the new node containing item after
                // the node that prev references
                Node newNode = new Node(item, prev.next);
                prev.next = newNode;
            } // end if
        } // end if
        else
        {

            throw new ListIndexOutOfBoundsException("List index out of bounds on add");
        } // end if
    } // end add

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

    public void removeAll()
    {
        //setting head to null causes list to be unreachable and thus
        //marked for garbage collection
        head = null;
    } // end removeAll

    //returns true if ListReferenceBased object is sorted else return false
    public boolean isSorted()
    {

    }

    //adjust the node references so that the items
    //are in reverse of the original order, without creating any new nodes
    public void reverseList()
    {

    }
}

___________________________________________________________________________________________________________________

class Node
{
    Comparable item;
    Node next;

    Node(Object newItem)
    {
        item = newItem;
        next = null;
    } // end constructor

    Node(Object newItem, Node nextNode)
    {
        item = newItem;
        next = nextNode;
    } // end constructor
} // end class Node

___________________________________________________________________________________________________________________

// *************************************
// Interface for the ADT List
// *************************************
public interface ListInterface
{
    //list operations:
    public boolean isEmpty();
    public int size();
    public void add(int index, Object item)
        throws ListIndexOutOfBoundsException;
    public void remove(int index)
        throws ListIndexOutOfBoundsException;
    public Object get(int index)
        throws ListIndexOutOfBoundsException;
    public void removeAll();
} // end ListInterface