// ****************************************************
// Reference-based implementation of ADT list using arrays.
// ****************************************************
public class List {
  // reference to linked list of items
 
  public static final int MAX_LIST = 20;
  public static final int NULL = -1;
 
  private ListItem item[] = new ListItem[MAX_LIST];  // data
  private int      next[] = new int[MAX_LIST];       // pointer to next item
 
  private int head;     // pointer to front of list
  private int free;     // pointer to front of free list
  private int numItems; // number of items in list
 
// Constructor must initialize used list to empty and free list to
// all available nodes.
 
  public List()
  {
    int index;
    for (index = 0; index < MAX_LIST-1; index++)
      next[index] = index + 1;
 
    next[MAX_LIST-1] = NULL;
 
    numItems = 0;
    head = NULL;
    free = 0;
  }  // end default constructor
 
  public void removeAll() {   // reinitialize all nodes to free
    int index;
    for (index = 0; index < MAX_LIST-1; index++)
      next[index] = index + 1;
 
    next[MAX_LIST-1] = NULL;
 
    numItems = 0;
    head = NULL;
    free = 0;
  } // end removeAll
 
  public boolean isEmpty() {
      return numItems == 0;
  }  // end isEmpty
 
  public int size() {
      return numItems;
  }  // end size
 
  private int 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
  // Postcondition: Returns a reference to the desired
  // node.
  // --------------------------------------------------
       int curr = head;
        for (int skip = 1; skip < index; skip++)
        {
          curr = next[curr];
        }
        return curr;
      }
 
  public ListItem get(int index)
  {
   if (index >= 1 && index <= numItems)
   {
     int curr = find(index);
     ListItem dataItem =item[curr];
     return dataItem;
   }
   else
   {
     System.out.println("List index out of bounds on get");
     return null;
   }
 } // end get
 
 
  public void add(int index, ListItem newItem)
  {
    if (index >= 1 && index <= numItems+1)
    {
     if (index == 1)
     {
          item[free]=newItem;
          int free2 = next[free];
 
          next[free]=head;
          head=free;
          free = free2;
      }
      else
      {
        int curr=free;
        int free2=next[free];
        int prev = find(index-1);
        int prev2=next[prev];
 
        next[prev]=curr;
        next[curr]=prev2;
        free=free2;
     }
     numItems++;
    }
    else
    {
      System.out.println("List index out of bounds on add");
    }
  }  
 
 
  public void remove(int index)
  {
    if (index >= 1 && index <= numItems)
    {
      if (index == 1)
      {
        int nextHead=next[head];
        next[head]=free;
        free=head;
        head=nextHead;
      }
      else
      {
        int prev = find(index-1);
        int curr=find(index);
        int getNext=find(index+1);
        next[prev]=getNext;
        next[curr]=free;
        free=curr;
      }
      numItems--;    
    } // end if
    else
    {
      System.out.println("List index out of bounds on remove");
    }
  }
}// end remove