Arrays and Linked Lists in java

Question

I've created four classes

• ObjectPool.java
• NodePool.java
• Node.java
• ArrayLinkedList.java

Class NodePool inherits from class ObjectPool and provides implementations of methods create() and reset().

Class Node has the usual doubly-linked list members: data, prev, and next. Class ArrayLinkedList implements a List of T elements. The data elements are stored in Nodes that are stored in the underlying ArrayList array.

Here is my code : ObjectPool.Java

abstract class ObjectPool<T> {
  protected Stack<T> pool;// Stack of pooled objects
  protected int maxSize; // max number of pooled objects (i.e., stack size)
  protected static final int DEFAULTMAXSIZE = 8;     

  ObjectPool(int maxSize);

  ObjectPool( );

  public void release(T x);

  public String toString();     

  public int size();   

  protected abstract T create();

  protected abstract T reset(T x);

  protected T allocate();
}

NodePool.Java

// Constructor invokes the constructor of the parent class.
  // Throws IllegalArgumentException if maxSize < 1
  NodePool(int maxSize);
 protected Node<T> create();
 protected Node<T> reset(Node<T> x);
}

ArrayLinkedList.java

class ArrayLinkedList<T> {
   public static void main(String args[]) {
      ArrayLinkedList<String> list = new
         ArrayLinkedList<String>();
      System.out.println("list.add(\"one\")");
      list.add("one");
      System.out.println();
      System.out.println("list:");
      System.out.println(list);
      list.dump();
      System.out.println();
      System.out.println("list.add(\"two\")");
      list.add("two");
      System.out.println();
      System.out.println("list:");
      System.out.println(list);
      list.dump();
      System.out.println();
      System.out.println("list.indexOf(\"one\"):" + 
        list.indexOf("one"));
      System.out.println("list.indexOf(\"two\"):" + 
        list.indexOf("two"));
      System.out.println("list.positionOf(\"one\"):" + 
        list.positionOf("one"));
      System.out.println("list.positionOf(\"two\"):" + 
        list.positionOf("two"));
      System.out.println();
      System.out.println("remove(new Integer(\"one\")");
      list.remove("one");
      System.out.println();
      System.out.println("list:");
      System.out.println(list);
      list.dump();
      System.out.println();
      System.out.println("add(\"three\")");
      list.add("three");
      System.out.println();
      System.out.println("list:");
      System.out.println(list);
      list.dump();
      System.out.println();
      System.out.println("add(\"four\")");
      list.add("four");
      System.out.println();
      System.out.println("list:");
      System.out.println(list);
      list.dump();
      System.out.println();
      // list is now: two three four
      // remove element at index 1, which is "three"
      System.out.println("remove(1)"); 
      list.remove(1);
      System.out.println();
      System.out.println("list:");
      System.out.println(list);
      list.dump();
      System.out.println();
      System.out.println("compress"); 
      list.compress();
      System.out.println();
      System.out.println("list:");
      System.out.println(list);
      list.dump();
      System.out.println();
      System.out.println("list.clear()");
      list.clear();
      System.out.println();
      System.out.println("list:");
      System.out.println(list);
      list.dump(); // array contains dummy node only
    }

 protected final static int NULL = -1;      
    protected ArrayList<Node<T>> array;
    protected NodePool<T> pool;
    protected int head; // position of dummy node in array
    protected int tail; // position of tail node in array
    protected int firstEmpty; // head of the list of empty nodes
    protected int numberEmpty; // number of empty nodes
    protected int size; // number of non-empty nodes
    protected int modCount; // number of modifications made
    protected final static int NODEPOOLSIZE = 8;

    // Constructor to initialize the data members, increment modCount,
    // create the dummy header Node, and add it to array
    public ArrayLinkedList();

    // Return number of non-empty nodes
    // Target Complexity: O(1)
    public int size();

    // convenience methods for debugging and testing
    protected int getFirstEmpty();  // return firstEmpty
    protected int getHead(); // return head
    protected int getTail(); // return tail
    protected ArrayList<Node<T>> getArray(); // return array

    // Appends the specified element to the end of this list. 
    // Returns true.
    // If no empty Nodes are available, then get a new Node from pool.
    // Throws IllegalArgumentException if e is null.
    // Checks assertions at the start and end of its execution.
    // Target Complexity: Amortized O(1)
    public boolean add(T e) {
        assert size>=0 && head==0 && numberEmpty >=0 && (numberEmpty==0  
         && firstEmpty==NULL) || (numberEmpty>0 && firstEmpty!=NULL)
          && (array.size() == size+numberEmpty+1);         
        ...

        // check this assertion before each return statement
        assert size>0 && head==0 && numberEmpty >=0 
          && (numberEmpty==0 && firstEmpty==NULL) || (numberEmpty>0 
            && firstEmpty!=NULL)
            && (array.size() == size+numberEmpty+1);
        return true;
    }

    // Inserts the specified element at the specified index in this list.  
    // Shifts the element currently at that index (if any) and any 
    // subsequent elements to the right (adds one to their indices).    
    // Throws IndexOutOfBoundsException if the index is out of range 
    // (index < 0 || index > size()).
    // Throws IllegalArgumentException if e is null.
    // Can call add(T e) if index equals size, i.e., add at the end
    // Checks assertions at the start and end of its execution.
    // Target Complexity: O(n)
    public void add(int index, T e) {
       assert size>=0 && head==0 && numberEmpty >=0 
         && (numberEmpty==0 && firstEmpty==NULL) || (numberEmpty>0 
           && firstEmpty!=NULL) && (array.size() == size+numberEmpty+1);

       ...

       // check this assertion before each return statement
       assert size>0 && head==0 && numberEmpty >=0 
         && (numberEmpty==0 && firstEmpty==NULL) || (numberEmpty>0 
             && firstEmpty!=NULL) && (array.size() == 
                 size+numberEmpty+1);
       return;
    }

    // Equivalent to add(0,e).
    // Throws IllegalArgumentException if e is null
    // Target Complexity: O(1)
    public void addFirst(T e);

    // Equivalent to add(e).
    // Throws IllegalArgumentException if e is null
    // Target Complexity: O(1)
    public void addLast(T e);

    // Add all of the elements (if any) in Collection c to the end 
    // of the list, one-by-one.
    // Returns true if this list changed as a result of the call.
    // Throws NullPointerException if the specified collection is null
    // Target Complexity: O(number of elements in c)
    public boolean addAll(Collection<? extends T> c);

    // Returns true if this list contains the specified element.
    // Throws IllegalArgumentException if e is null
    // May call indexOf(e)
    // Target Complexity: O(n)
    public boolean contains(T e);


    // Returns the index of the first occurrence of the 
    // specified element in this list,
    // or NULL if this list does not contain the element.
    // Throws IllegalArgumentException if e is null
    // Target Complexity: O(n)
    public int indexOf(T e);

   // Returns the array position of the first occurrence of 
   // the specified element in array
   // or NULL (-1) if this list does not contain the element. 
   // Note that the return value is a position in the array, 
   // not the index of an element in the list.
   // Called by remove(T e) to find the position of e in the array.
   // Throws IllegalArgumentException if e is null
   // Target Complexity: O(n)
   protected int positionOf(T e);

    // Returns the element at the specified index in this list.
    // Throws IndexOutOfBoundsException if the index is out 
    // of range (index < 0 || index >= size())
    // Target Complexity: O(n)
    public T get(int index);

    // Returns the first element in the list.
    // Throws NoSuchElementException if the list is empty
    // Target Complexity: O(1)
    public T getFirst();

    // Returns the last element in the list
    // Throws NoSuchElementException if the list is empty
    // Target Complexity: O(1)
    public T getLast();

    // Remove the node at position current in the array.
    // Note that current is a position in the array, not the 
    // index of an element in the list.
    // The removed node is made empty and added to the front 
    // of the list of empty Nodes. Dummy node cannot be removed.
    // Called by remove(T e) and remove(int index) to 
    // remove the target Node.
    // Target Complexity: O(1)
    protected void removeNode(int current) {
       assert current > 0 && current < array.size();
       . . .
    }

    // Removes the first occurrence of the specified element from 
    // this list, if it is present. Returns true if this
    // list contained the specified element.
    // Throws IllegalArgumentException if e is null.
    // Checks assertions at the start and end of its execution.
    // Target Complexity: O(n)
    public boolean remove(T e) {

       assert size>=0 && head==0 && numberEmpty >=0
        && (numberEmpty==0 && firstEmpty==NULL) || (numberEmpty>0 
          && firstEmpty!=NULL) && (array.size() == size+numberEmpty+1);

       ...

       // check this assertion before each return statement
       assert size>=0 && head==0 && numberEmpty >=0 
         && (numberEmpty==0 && firstEmpty==NULL) || (numberEmpty>0 
          && firstEmpty!=NULL) && (array.size() == size+numberEmpty+1);
       return true;
    }

    // Removes the element at the specified index in this list.
    // Shifts any subsequent elements to the left (subtracts one from
    // their indices). Returns the element that was removed from the 
    // list. Throws IndexOutOfBoundsException if the index is 
    // out of range (index < 0 || index >= size)
    // Checks assertions at the start and end of its execution.
    // Target Complexity: O(n)
    public T remove(int index) {
      assert size>=0 && head==0 && numberEmpty >=0 
        && (numberEmpty==0 && firstEmpty==NULL) || (numberEmpty>0 
          && firstEmpty!=NULL) && (array.size() == size+numberEmpty+1);

       ...

        // check this assertion before each return statement
       assert size>=0 && head==0 && numberEmpty >=0 && (numberEmpty==0 
        && firstEmpty==NULL) || (numberEmpty>0 && firstEmpty!=NULL) 
        && (array.size() == size+numberEmpty+1);
        return … ;
    }

    // Returns the first element in the list.
    // Throws NoSuchElementException if the list is empty.
    // Equivalent to remove(0), for index 0
    // Target Complexity: O(1)
    public T removeFirst();

    // Returns the last element in the list
    // Throws NoSuchElementException if the list is empty
    // Equivalent to remove(size-1), for index size-1
    // Target Complexity: O(1)
    public T removeLast();

    // Returns true if the Node at the specified position in the 
    // array is an empty node. The dummy node is never considered to be
    // an empty node.
    // Target Complexity: O(1)
    protected boolean positionIsEmpty(int position) {
      assert position > 0 && position < array.size();

    }

    // Returns number of empty nodes.
    // Target Complexity: O(1)
    protected int numEmpty();

    // Replaces the element at the specified position in this 
    // list with the specified element. Returns the element 
    // previously at the specified position.    
    // Throws IllegalArgumentException if e is null.
    // Throws IndexOutOfBoundsException if index is out of 
    // range (index < 0 || index >= size)
    // Target Complexity: O(n)
    public T set(int index, T e);

    // Removes all of the elements from this list. 
    // The list will be empty after this call returns.
    // The array will only contain the dummy head node.
    // Some data members are reinitialized and all Nodes
    // are released to the node pool. modCount is incremented.
    // Target Complexity: O(n)
    public void clear() {
       assert size>=0 && head==0 && numberEmpty >=0 
        && (numberEmpty==0 && firstEmpty==NULL) || (numberEmpty>0 
        && firstEmpty!=NULL) && (array.size() == size+numberEmpty+1);

       ...

       // check this assertion before each return statement
       assert size==0 && head==0 && numberEmpty==0 && firstEmpty==NULL
       && (array.size() == size+numberEmpty+1);
       return;
    }

    // Returns an Iterator of the elements in this list, 
    // starting at the front of the list
    // Target Complexity: O(1)
    Iterator<T> iterator();

    // Convenience debugging method to display the internal 
    // values of the list, including ArrayList array
    protected void dump() {
      System.out.println();
      System.out.println("**** dump start ****");
      System.out.println("size:" + size);
      System.out.println("number empty:" + numberEmpty);
      System.out.println("first empty:"+firstEmpty);
      System.out.println("head:" + head);
      System.out.println("tail:" + tail); 
      System.out.println("list:");
      System.out.println("array:");
      for (int i=0; i<array.size(); i++) // show all elements of array
         System.out.println(i + ": " + array.get(i));
      System.out.println("**** dump end ****");
      System.out.println();
    }

    // Returns a textual representation of the list, i.e., the 
    // data values of the non-empty nodes in list order.
    public String toString();

    // Compress the array by releasing all of the empty nodes to the 
    // node pool.  A new array is created in which the order of the 
    // Nodes in the new array matches the order of the elements in the 
    // list. When compress completes, there are no empty nodes. Resets 
    // tail accordingly.
    // Target Complexity: O(n)
    public void compress();

    // Iterator for ArrayLinkedList. (See the description below.)
    private class ArrayLinkedListIterator implements Iterator<T> {
      // Constructor
      // Target Complexity: O(1)
      public ArrayLinkedListIterator ();

      // Returns true if the iterator can be moved to the next() element.
      public boolean hasNext();

      // Move the iterator forward and return the passed-over element
      public T next();

      // The following operation is part of the Iterator interface 
      // but is not supported by the iterator. 
      // Throws an UnsupportedOperationException if invoked.
      public void remove();
   }
}

The problem is ,few things are not completed in the code ,i dont know what to do . Kindly correct me what I'm doing wrong.

Answer 1

Inside dump method, The only place where you can get a NPE is array.size() In your ArrayLinkedList class, array is initialized to null and the same is also not being initialized in constructor as well.

protected ArrayList<Node<T>> array;

You need to initialize array inside constructor.

public ArrayLinkedList(){
    array = new ArrayList<>();
}