Dynamic arrays

http://www.algolist.net/Data_structures/Dynamic_array

public class DynamicArray {

      private int[] storage;

      private int size;

      public DynamicArray() {

            storage = new int[10];

            size = 0;

      }

      public DynamicArray(int capacity) {

            storage = new int[capacity];

            size = 0;

      }

}

Capacity management: Ensure Capacity, Pack
Pack
When items are removed, amount of the free space increases. If there are too few values in the dynamic array, unused storage become just a waste of space. For the purpose of saving space, we develop a mechanism to reduce capacity, when it is excessive.

• check, if size is less or equal, than half of the capacity;
• calculate new capacity by the formula: newCapacity = (size * 3) / 2 + 1. Algorithm leaves exact the amount of space, as if storage capacity had been trimmed to the size and then method to ensure capacity was called.

Lower boundary for size, after which packing is done, may vary. In the current example it is 0.5 of the capacity value. Commonly, pack is a private method, which is called after removal. Also, dynamic array interface provides a trim method, which reduces capacity to fit exact amount of items in the array. It is done from the outside of the implementation, when you are sure, that no more values to be added (for instance, input from user is over).

      public void ensureCapacity(int minCapacity) {

            int capacity = storage.length;

            if (minCapacity > capacity) {

                  int newCapacity = (capacity * 3) / 2 + 1;

                  if (newCapacity < minCapacity)

                        newCapacity = minCapacity;

                  storage = Arrays.copyOf(storage, newCapacity);

            }

      }

      private void pack() {

            int capacity = storage.length;

            if (size <= capacity / 2) {

                  int newCapacity = (size * 3) / 2 + 1;

                  storage = Arrays.copyOf(storage, newCapacity);

            }

      }

      public void trim() {

            int newCapacity = size;

            storage = Arrays.copyOf(storage, newCapacity);

      }

http://www.algolist.net/Data_structures/Dynamic_array/Access_functions
InsertAt
This operation may require array expanding, so algorithm invokes ensure capacity method first, which should ensure size + 1 minimal capacity. Then shift all elements from i to size - 1, where i is the insertion position, one element right. Note, that if new element is inserted after the last element in the array, then no shifting required. After shifting, put the value to i-th element and increase size by one.

RemoveAt
Shift all elements from i to size - 1, where i is the removal position, one element left. Then decrease size by 1 and invoke pack opeartion. Packing is done, if there are too few elements left after removal.

      private void rangeCheck(int index) {

            if (index < 0 || index >= size)

                  throw new IndexOutOfBoundsException("Index: " + index + ", Size: "

                             + size);

      }

     

      public void set(int index, int value)

      {

            rangeCheck(index);

            storage[index] = value;

      }

     

      public int get(int index)

      {

            rangeCheck(index);

            return storage[index];

      }

      public void removeAt(int index) {

            rangeCheck(index);

            int moveCount = size - index - 1;

            if (moveCount > 0)

                  System.arraycopy(storage, index + 1, storage, index, moveCount);

            size--;

            pack();

      }

      public void insertAt(int index, int value) {

            if (index < 0 || index > size)

                  throw new IndexOutOfBoundsException("Index: " + index + ", Size: "

                             + size);

            ensureCapacity(size + 1);

            int moveCount = size - index;

            if (moveCount > 0)

                  System.arraycopy(storage, index, storage, index + 1, moveCount);

            storage[index] = value;

            size++;

      }