A Dynamic Array Class in Java

Design a Class for Dynamic Arrays

In Java, the size of an array is fixed when it is created. Elements are not allowed to be inserted or removed. However, it is possible to implement a dynamic array by allocating a new array and copying the contents from the old array to the new one.

A dynamic array has variable size and allows elements to be added or removed. For this, we can allocate a fixed-size array and divide it into two parts:

• the first part stores the elements of the dynamic array and
• the second part is reserved, but not used.

Then we can add or remove elements at the end of the array by using the reserved space, until this space is completely consumed. After that, we create a bigger array and copy the contents of the old array to the new one.

• Logical size (size): the number of elements in the dynamic array
• Capacity: the physical size of the internal array (the maximum possible size without relocating storage)

We now design a class DynamicArray represents dynamic arrays of integers. It has two attributes:

• int[] data: an integer array, and
• int size: the logical size, the number of elements used

The capacity of this dynamic array is simply data.length.

An important method we need is to add elements to the end of the dynamic array. This method should provide automatic extension if the capacity is not large enough to hold the added element.

In summary, we wish to design the class DynamicArray with the following members:

Attributes / Constructors / Methods:

• int[] data: the array storing the elements
• int size: the number of elements
• DynamicArray(): initialize this dynamic array with size 0
• DynamicArray(int capacity): initialize this dynamic array with the capacity
• int get(int index): get the element at the specified index
• int set(int index, int element): set the value of the element at the specified index
• boolean add(int element): add the element to the end of the array
• void ensureCapacity(int minCapacity): increase the capacity
• int size(): return the size of the dynamic array
• boolean isEmpty(): check whether the array is empty
• void clear(): clean up the elements

Implement the DynamicArray Class

The following contains the implementation of the class.

import java.util.Arrays;

public class DynamicArray
{
  // The storage for the elements. 
  // The capacity is the length of this array.
  private int[] data;
  
  // The number of elements (logical size).
  // It must be smaller than the capacity.
  private int size;
  
  // Constructs an empty DynamicArray
  public DynamicArray()
  {
    data = new int[16];
    size = 0;
  }
  
  // Constructs an empty DynamicArray with the
  // specified initial capacity.
  public DynamicArray(int capacity)
  {
    if (capacity < 16)
    capacity = 16;
    data = new int[capacity];
    size = 0;
  }
  
  // Increases the capacity, if necessary, to ensure that
  // it can hold at least the number of elements
  // specified by the minimum capacity argument.
  public void ensureCapacity(int minCapacity)
  {
    int oldCapacity = data.length;
    if (minCapacity > oldCapacity)
    {
      int newCapacity = (oldCapacity * 2);
      if (newCapacity < minCapacity)
        newCapacity = minCapacity;
      data = Arrays.copyOf(data, newCapacity);
    }
  }
  
  // Returns the logical size
  public int size()
  {
    return size;
  }
  
  public boolean isEmpty()
  {
    return size == 0;
  }
  
  // Checks if the given index is in range.  
  private void rangeCheck(int index)
  {
    if (index >= size || index < 0)
      throw new IndexOutOfBoundsException("Index: " + 
            index + ", Size: " + size);
  }
  
  // Returns the element at the specified position.
  public int get(int index)
  {
    rangeCheck(index);
    return data[index];
  }
  
  // Appends the specified element to the end.
  public boolean add(int element)
  {
    ensureCapacity(size + 1);
    data[size++] = element;
    return true;
  }
  
  // Removes all of the elements.
  public void clear()
  {
    size = 0;
  }
  
  // Replaces the element at the specified position
  public int set(int index, int element)
  {
    rangeCheck(index);
    int oldValue = data[index];
    data[index] = element;
    return oldValue;
  }
  
  public int capacity()
  {
    return data.length;
  }
}

Note that, the ArrayList class in the standard Java library uses essentially the same ideas as this example.

Related Posts

• A Queue Class in Java
• A Stack Class in Java

Comments

comments