title: List Manipulation with references
body: <p>So for my assignment we are to implement some referenced based list manipulation methods in a class and then add to a list and demonstrate the methods using a driver file. </p>
  
  <p>I have provided the entire program for download which includes a <code>pdf</code> that explains the assignment. Our professor uploaded a completed driver file and mine is exactly the same as his but I am getting some run-time errors, first is when calling <code>add()</code> for the third time I get a <code>NullPointerException</code>, if I comment out the rest of the <code>add()</code> calls, <code>size()</code> will not return the same size as <code>getSize()</code> and <code>getSizeRecursive().</code> </p>
  
  <p>Please Help me. Link to download: <a href="https://www.dropbox.com/s/qe771q3156h9nwx/ListReferenceBased.rar" rel="nofollow">https://www.dropbox.com/s/qe771q3156h9nwx/ListReferenceBased.rar</a></p>
  
  <pre><code>// ****************************************************
  // 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
  
  public ListReferenceBased() {
      numItems = 0;
      head = null;
  }  // end default constructor
  
  public boolean isEmpty() {
      return numItems == 0;
  }  // end isEmpty
  
  public int size() {
      return numItems;
  }  // end size
  
  private Node find(int index) {
      // --------------------------------------------------
      // Locates a specified node in a linked list.
      // Precondition: index is the array index of the desired node.
      // Assumes that 0 &lt;= index &lt; numItems
      // Postcondition: Returns a reference to the desired node.
      // --------------------------------------------------
      Node curr = head;
      for (int skip = 0; skip &lt; index; skip++) {
          curr = curr.getNext();
      } // end for
      return curr;
  } // end find
  
  public Object get(int index)
  throws ListIndexOutOfBoundsException {
      if (index &gt;= 0 &amp;&amp; index &lt; numItems) {
          // get reference to node, then data in node
          Node curr = find(index);
          Object dataItem = curr.getItem();
          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 &gt;= 0 &amp;&amp; index &lt;= numItems) {
          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.getNext());
              prev.setNext(newNode);
          } // end if
          numItems++;
      }
      else {
          throw new ListIndexOutOfBoundsException(
          "List index out of bounds on add");
      } // end if
  }  // end add
  
  public void remove(int index)
  throws ListIndexOutOfBoundsException {
      if (index &gt;= 0 &amp;&amp; index &lt; numItems) {
          if (index == 0) {
              // 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
          numItems--;
      } // 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
  
  
  // TO IMPLEMENT
  public String toString(){
      Node curr = head;
      String str = new String("");
      while(curr != null){
          str += curr.getItem() + ", ";
          curr = curr.getNext();
      }
      return str;
  }
  
  
  // TO IMPLEMENT
  public void reverse(){
      Node prev = null;
      Node curr = head;
      while(curr != null){
          Node next = curr.getNext();
          curr.setNext(prev);
          prev = curr;
          curr = next;
      }
      head = prev;
  }
  
  
  // TO IMPLEMENT
  // This is a helper method, so try to define your own method
  // that this helper will call.
  public void reverseRecursive(){
      Node prev = null;
      Node curr = head;
      reverseRecursiveHelper(prev, curr);
      head = prev;
  }
  public Object reverseRecursiveHelper(Node prev, Node curr){
      if(curr == null)
      return null;
      else {
          Node next = curr.getNext();
          curr.setNext(prev);
          prev = curr;
          curr = next;
          return reverseRecursiveHelper(prev, curr);
      }
  }
  
  
  // TO IMPLEMENT
  public int getSize()
  // --------------------------------------------------
  // Returns the number of items in a linked list.
  // Precondition: head points to the first element
  // in a list of type node.
  // Postcondition: The number of items in the list
  // is returned.
  // --------------------------------------------------
  {
      int count = 0;
      Node curr = head;
      while(curr != null){
          curr = curr.getNext();
          count++;
      }
      return count;
  }
  
  
  // TO IMPLEMENT
  public int getSize(Node cur)
  // --------------------------------------------------
  // Returns the number of items in a linked list.
  // The initial call should have the beginning of the list
  // as it's input argument, i.e. listCount(head);
  // Precondition: cur points to a list of type node
  // Postcondition: The number of items in the list
  // is returned.
  // --------------------------------------------------
  {
      if(cur != null)
      return 1 + getSize(cur.getNext());
      else //base case
          return 0;
  
  }
  
  
  // TO IMPLEMENT
  public int getSizeRecursive()
  {
      return getSize(head);
  }
  
  
  // TO IMPLEMENT
  public Node findMToLast(int m){
      Node current = head;
      if(current == null)
      return null;
      for(int i = 0; i &lt; m; i++)
      if(current.getNext() != null)
      current = current.getNext();
      else
          return null;
      Node mBehind = head;
      while (current.getNext() != null){
          current = current.getNext();
          mBehind = mBehind.getNext();
      }
      return mBehind;
  }
  
  
  } // end ListReferenceBased
  </code></pre>
  
  <p>Driver:</p>
  
  <pre><code>// ********************************************************
  // Test Reference-based implementation of the ADT list.
  // *********************************************************
  public class TestListReferenceBased {
  
  
  
  static public void main(String[] args)
  {
      ListReferenceBased aList = new ListReferenceBased();
  
      aList.add(0, new Integer(1));
      aList.add(1, new Integer(2));
      aList.add(2, new Integer(3));
      aList.add(3, new Integer(4));
      aList.add(4, new Integer(5));
      aList.add(5, new Integer(6));
  
      System.out.println("size() and get(i): ");
      for (int i = 0; i &lt; aList.size(); i++)
          System.out.println(aList.get(i) + " ");
      System.out.println();
  
      System.out.println("Size with size() = " + aList.size());
      System.out.println("Size with getSize() = " + aList.getSize());
      System.out.println("Size with getSizeRecursive() = " + aList.getSizeRecursive());
  
      System.out.println("Initial List = " + aList);
      aList.reverse();    // iterative version
      System.out.println("Reverse with reverse() = " + aList);
  
      System.out.println("====================================");
  
      aList.reverseRecursive();   // recursive version
      System.out.println("Reverse with reverseRecursive() = " + aList);
  
          int offset = 3;
      Node node = aList.findMToLast(offset);
      if (node != null)
          System.out.println(offset + "-th node to the last node contains " +  node.getItem() + ".");
      else
          System.out.println("Offset(=" + offset + ") to the last node is greater than list size(=" + aList.size() + ").");
  
  } // end main
  
  }  // end TestListReferenceBased
  </code></pre>
  
  <p>Stack trace is:</p>
  
  <pre><code>Exception in thread "main" java.lang.NullPointerException at
      ListReferenceBased.add(ListReferenceBased.java:63) at
      TestListReferenceBased.main(TestListReferenceBased.java:14)
  </code></pre>