Making a Dynamic Array for a class without using Arraylists in Java and have not been properly taught how to do it

This is a great programming assignment to give students a clear understanding of ArrayList. As you might have already guessed your instructor wants you to implement ArrayList of your own and its a wonderful way to teach Data Structure.

Starting with the requirements one by one

• Constructor with parameter : The intention is that you can initialize an array of specific length. However, since the array has no element keep its size as 0

  public DynamicArray (int capacity) { if (capacity < 0) { throw new IllegalArgumentException("Size cannot be less than 0."); } this.array = new int[capacity]; this.size = 0 }

• Constructor with no parameter : Similar as previous just that capacity will be replaced with a constant value of 10. It makes complete sense for the sake of legibility that you assign this constant as

  public static final int DEFAULT_CAPACITY = 10;

  • For shrink/increase of capacity during push or pop, think it this way, if you know your cookie jar would soon run out of space what will you do. You will get a new jar. Now, how do you decide what size of jar you want ? Well here the answer is double if you want to go bigger and 1/4 if you want to go smaller. Getting a new jar is analogous to creating a new integer array object. You then move all your cookies from small to bigger jar and discard the jar. Similarly, copy each item from the old array to new array.

This answer could be rather long and I know it would be cheating if I pass on the source code to you, but as I understand you are really willing to see how it is to be done and hence you can look up the reference implementation of ArrayList : http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/ArrayList.java

This initially might be intimidating but if you carefully look at methods grow(), ensureCapacity(), indexOf(), clone(), add() you will get a better idea of how it is implemented in java

Let's start over again. From the beginning. I will comment each step in this tutorial. (Note that this question is usually far too broad to be answered, but today I am going to do that nevertheless.)

This assignment, we are supposed to make a Dynamic Array of Integers class with Constructors, Methods, and required features.

Let's start with the class itself:

public final class DynamicArray {
}

This is the part, you have already done. Everything that follows now (fields, methods) will be part of that class. One note: I have made that class final to prevent subclassing, which would otherwise introduce some other problems.

private int array[] field. You MUST store the data internally in a regular partially-filled array of integers. Please DO NOT USE ArrayList. The size of the allocated array is its capacity and will be discussed below.

You have also already done this:

private int[] array;

Note, that I usually would mark that field as private. But as some other requirements are too grow and shrink that array, we cannot do that.

private int size field. This variable stores the number of “occupied” elements in the array. Set to 0 in the constructor.

You also have already done this:

private int size;

The requirement to "set to 0 in the constructor" is superfluous, because in Java such fields are initialized to their default value (which is 0 in this case). That means, whenever you create an instance of your DynamicArray class, the field size will automatically have a value of 0. I will therefore not set the size in the following constructors.

Constructor with parameter. The parameter defines the capacity of initial array. Allocates array of given capacity, sets size field to zero. In case the parameter given to constructor is less than 0, IllegalArgumentException is being thrown.

Although you already have shown us the constructor, you forgot to initialize the array. Here we go:

public DynamicArray(int capacity) {
    if (capacity < 0)
        throw new IllegalArgumentException("Capacity cannot be less than 0.");
    array = new int[capacity];
}

I would argue that even a capacity of 0 does not make much sense, but we can deal with that later (when the array shall grow).

No-argument constructor. Allocates array of size 10, sets size field to 0.

You have already shown the constructor, but you should use constructor chaining, because you already have another constructor that handles the initialization.

public DynamicArray() {
    this(10);
}

It is even better to have a constant for that:

private static final int DEFAULT_CAPACITY = 10;

public DynamicArray() {
    this(DEFAULT_CAPACITY);
}

Copy constructor. The constructor takes an object of type DynamibcArray as a parameter and copies it into the object it creates. The constructor throws IllegalArgumentException if the object that was passed to copy from is null.

Unfortunately, you got this one wrong. A copy constructor takes another DynamicArray (not an int[]).

public DynamicArray(DynamicArray source) {
    if (source == null)
        throw new IllegalArgumentException("Source array must not be null.");
    this.array = Arrays.copyOf(source.array, source.array.length);
    this.size = source.size;
}

This uses the helper class java.util.Arrays to create a copy of the internal array.

int getSize() returns the size – a number of occupied elements in the array.

Ok. This one's easy:

public int getSize() {
    return size;
}

int [] toArray() accessor returns the array. Make sure you DO NOT return the private array field. Instead, allocate memory for the new array, copy your array field into that new object, and return the new array.

Although you have this method, you forgot to make a copy of the internal array. You are not allowed to return that. And you should not return that, because any caller then could change your internal array. So we are going to use the same technique as in the copy constructor:

public int[] toArray() {
    return Arrays.copyOf(array, array.length);
}

public void push(int num) adds a new element to the end of the array and increments the size field. If the array is full, you need to increase the capacity of the array.

This method has much to do. So you should use some helper method, e.g. for the growing functionality.

public void push(int num) {
    growIfNecessary();
    array[size] = num;
    size += 1;
}

Some explanation: I am postponing the growing functionality for now (so I extracted it into another method that I will show later). For pushing the given number into the internal array, you must know the exact position. Fortunately the size field tells you exactly that, but you also have to increment that pointer. You could also do it that way:

public void push(int num) {
    growIfNecessary();
    array[size++] = num;
}

public int pop() throws RuntimeException removes the last element of the array and returns it. Decrements the size field. If the array is empty a RuntimeException with the message “Array is empty” must be thrown. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array.

public int pop() {
    if (size == 0)
        throw new NoSuchElementException();
    int result = array[--size];
    shrinkIfNecessary();
    return result;
}

Hint: I am throwing another exception which is more appropriate for that case. Popping an element is the opposite function of pushing one. We are first decrementing the pointer, then reading and returning the value. Additionally, I extracted the shrinking functionality into another method that I will also show later.

int get(int index) throws IndexOutOfBoundsException returns element of the array with the requested index. If the index provided is too large or negative, the IndexOutOfBoundsException is thrown with the message "Illegal index".

You got this one completely right:

public int get(int index) throws IndexOutOfBoundsException {
    if (index >= size || index < 0)
        throw new IndexOutOfBoundsException("Illegal index");
    return array[index];
}

int indexOf(int key) returns the index of the first occurrence of the given number. Returns -1 when the number is not found.

With this method you shall search for a given number in the array. It needs a loop!

public int indexOf(int key) {
    for (int i = 0; i < size; i++)
        if (array[i] == key)
            return i; // found
    return -1; // not found
}

void add(int index, int num) throws IndexOutOfBoundsException adds a new element (passed as parameter num) to the location of the array specified by index parameter. If the index is larger than size of the array or less than 0, IndexOutOfBoundsException is thrown. When adding the element into the middle of the array, you’ll have to shift all the elements to the right to make room for the new one. If the array is full and there is no room for a new element, the array must be doubled in size. Please follow the steps listed in the push() method description to double the capacity of the array.

This one is somewhat advanced, as it needs shifting the elements, which you did not do in your attempt. So let's go:

public void add(int index, int num) throws IndexOutOfBoundsException {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException("Illegal index");
    growIfNecessary();
    System.arraycopy(array, index, array, index + 1, size - index);
    array[index] = num;
    size += 1;
}

Explanation: The index checking must now check whether the index is greater than the size (not greater or equal), because you also can add an element at the end of the array (at the position that size points to). We then have to grow the array if necessary (like in the push method). Then I use a Java built-in class for shifting all elements one position to the rigth from the given index to the end. The last step is to add the element at the given index, and we must not forget to increment the size.

int remove ( int index) throws IndexOutOfBoundsException removes the element at the specified position in this array. When the element is removed from the middle of the array, all the elements must be shifted to close the gap created by removed element. If the index value passed into the method is more or equal to the size or less than 0 the IndexOutOfBoundsException must be thrown. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array.

This one is the most difficult method. I will show you directly the whole thing:

public int remove(int index) {
    if (index >= size || index < 0)
        throw new IndexOutOfBoundsException("Illegal Index");
    int result = array[index];
    System.arraycopy(array, index + 1, array, index, size - index - 1);
    size -= 1;
    shrinkIfNecessary();
    return result;
}

We first have to check the index, then we can get the element that later will be returned by this method. Now comes the shifting: We shift all elements from position index + 1 to the end one place to the left. We then decrement the size and shrink the internal array if necessary. That's it.

Now I am going to show you the last two helper methods.

Let's start with the growing method:

a. Create a new array with the size equal to double the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Add the new element to the end of the new array. d. Use new array as an array field.

private void growIfNecessary() {
    if (size == array.length) {
        if (array.length == 0)
            array = new int[1]; // Special case for capacity 0.
        else
            array = Arrays.copyOfRange(array, 0, array.length * 2);
    }
}

The array is full, if the size equals the capacity. Again, I am using the Arrays helper class. The copyOfRange method is able to create a larger array.

Now to the shrinking method:

a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field.

private void shrinkIfNecessary() {
    if (size * 4 <= array.length)
        array = Arrays.copyOfRange(array, 0, array.length / 2);
}

Here, we do not have any special case. Simply shrink the array, if the capacity is 4 times larger than the size. That's it.

Study the code carefully and try to reproduce the code. The usage of library methods (System.arraycopy and Arrays.copyOf) can easily be replaced by simple for loops using temporary arrays. Try it out.

public int pop() throws RuntimeException removes the last element of the array and returns it. Decrements the size field. If the array is empty a RuntimeException with the message “Array is empty” must be thrown. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array:

a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field.

at the moment, your pop command is just running itself, recursively. This will crash.

Edit: I recommend partially implementing remove before pop, as it will make pop easier.

Lets break this down into a bullet point list and examine each item. (Also I recommend making a new question for each specific piece of advice you need)

1. public int pop() throws RuntimeException
2. removes the last element of the array and returns it.
3. Decrements the size field.
4. If the array is empty a RuntimeException with the message “Array is empty” must be thrown.
5. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array:
6. a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field.

Now I've broken this down into sections, to start with I would ignore 3, 4, 5, 6

and just implement a super dumb pop method that just removes the last element from the array.

Once you have that working, concentrate on the edge cases.

3. Decrements the size field This is going to be a cross cutting concern across your class. You will want to do this only in a small reuseable part of your code, as you are going to be messing with the the size field every time an element gets added or removed.

4. If the array is empty a RuntimeException with the message "Array is empty" must be thrown. You will want to tackle this at the very start of your pop method, as it's a guard clause protecting invalid use.

5.At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array: Again, this is probably going to be a recurring cross cutting concern, so defining this as a separate private method that gets reused will be helpful.

6. a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field. Is providing guidance on how best to implement 5.

you can find more information on array copying and stuff over on the docs of the Arrays static helper class. https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html as well as the arrayCopy method in System https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#arraycopy(java.lang.Object,%20int,%20java.lang.Object,%20int,%20int)