java - Java中的数组和链表

This question already has answers here:

What is a NullPointerException, and how do I fix it?

（12个答案）


4年前关闭。




我开了四个班


ObjectPool.java
NodePool.java
节点java
ArrayLinkedList.java


NodePool类从ObjectPool类继承，并提供方法create（）和reset（）的实现。

类节点具有通常的双向链接列表成员：数据，上一个和下一个。 ArrayLinkedList类实现T元素的列表。数据元素存储在存储在基础ArrayList数组中的Node中。

这是我的代码：
对象池

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();
}

节点池

// 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();
   }
}

问题是，代码中很少有事情没有完成，我不知道该怎么办。请纠正我我在做什么错。

最佳答案

在内部转储方法中，唯一可以获得NPE的地方是array.size()
在您的ArrayLinkedList类中，array初始化为null，同样在构造函数中也未初始化。

protected ArrayList<Node<T>> array;

您需要在构造函数中初始化array。

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