ListReferenceBased

class Node
{
    Object 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

// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

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

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

    public boolean isEmpty()
    {
        return numItems == 0;
    } // end isEmpty

    public int size()
    {
        return numItems;
    } // end size

    public 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 <= numItems+1
    // 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 Object get(int index) throws ListIndexOutOfBoundsException
    {
        if (index >= 0 && index < numItems)
        {
            // get reference to node, then data in node
            Node curr = find(index);
            Object 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, Object item) throws ListIndexOutOfBoundsException
    {
        if (index >= 0 && index < numItems+1)
        {
            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
            numItems++;
        } // 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 && index < numItems)
        {
            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;
        numItems = 0;
    } // end removeAll
} // end ListReferenceBased