4
\$\begingroup\$

I am implementing a class to mimic dynamic array as a part of my learning process of data structures. I have written the following class which works as a dynamic array data structure.

I have gone through some video tutorials and also read some code from Java's ArrayList implementation to understand how to code it in a simple manner. I would like to get the code reviewed from the following perspective:

  1. Is there any design pattern that I should be following
  2. Improvements like removing compile time warning related to generics.
  3. Any tips on including test cases that can expose hidden issues in the code
  4. Any other tips that will make it a better code like improve its performance or make it more modular.
import java.util.Arrays;
import java.util.Iterator;

public class DynamicArray<T> implements Iterable<T> {
  private Object[] elements;
  private int length = 0;
  private int capacity = 0;

  public DynamicArray() {
    this(10);
  }

  public DynamicArray(int capacity) {
    this.capacity = capacity;
    this.length = 0;
    this.elements = new Object[capacity];
  }

  public int size() {
    return length;
  }

  public boolean isEmpty() {
    return size() > 0;
  }

  public T get(int index) {
    validateIndexValue(index);
    return (T)elements[index];
  }

  public void set(int index, T element) {
    validateIndexValue(index);
    elements[index] = element;
  }

  public void clear() {
    for(int i = 0; i < length; i++) {
      elements[i] = null;
    }
    length = 0;
  }

  public boolean add(T element) {
    ensureCapacity(length + 1);
    elements[length++] = element;
    return true;
  }

  public T removeAt(int index) {
    validateIndexValue(index);
    T element = (T) elements[index];
    removeElement(index);
    return element;
  }

  public boolean remove(T element) {
    if(element == null) {
      for(int i = 0; i < length; i++) {
        if(elements[i] == null) {
          removeElement(i);
          return true;
        }
      }
    } else {
      for(int i = 0; i < length; i++) {
        if(element.equals(elements[i])) {
          removeElement(i);
          return false;
        }
      }
    }
    return false;
  }

  public int indexOf(T element) {
    if(element == null) return -1;
    for(int i = 0; i < length; i++) {
      if(element.equals(elements[i])) {
        return i;
      }
    }
    return -1;
  }

  public boolean contains(T element) {
    return indexOf(element) > -1;
  }

  public java.util.Iterator<T> iterator() {
    return new java.util.Iterator<T>() {
      int index = 0;
      public boolean hasNext() {
        return index < length;
      }

      public T next() {
        return (T) elements[index++];
      }
    };
  }

  private void removeElement(int index) {
    int elementsToMove = length - index - 1;
    if(elementsToMove > 0) {
      System.arraycopy(elements, index + 1, elements, index, elementsToMove);
    }
    elements[--length] = null;
  }

  private void ensureCapacity(int minSize) {
    if(minSize >= capacity) {
      capacity *= 2;
      elements = Arrays.copyOf(elements, capacity);
    }
  }

  private void validateIndexValue(int index) {
    if(index >= length || index < 0) {
      throw new IllegalArgumentException("Bad index value passed : " + index);
    }
  }
}
```
New contributor
devi prasad is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
2
  • \$\begingroup\$ element.equals(elements[i] == null) - do you really mean it? \$\endgroup\$ – vnp Feb 22 at 23:20
  • \$\begingroup\$ Sorry @vnp , missed it while adding the code in the question. Changed it now \$\endgroup\$ – devi prasad Feb 23 at 3:02
2
\$\begingroup\$

Unit testing

Definitely write some test cases for your code. JUnit would be one possibility, but there are many test frameworks to choose from.

With any test framework, and at least one test per public method, this goof would have been immediately apparent:

  public boolean isEmpty() {
    return size() > 0;
  }

As Timothy Truckle points out in a comment below, one test per public method is not enough.

Misleading method argument name/implementation

While the way that you used ensureCapacity(length + 1) will work, it hides a subtle bug.

  private void ensureCapacity(int minSize) {
    if(minSize >= capacity) {
      capacity *= 2;
      elements = Arrays.copyOf(elements, capacity);
    }
  }

Consider if you exposed the method ensureCapacity(int minSize) as a public method, like the standard library's ArrayList#ensureCapacity method. A caller might use:

  var container = new DynamicArray<Integer>();
  container.ensureCapacity(10000);
  // ...

The first statement creates the container, with an initial capacity of 10. The next statement looks to resize the container to hold 10000 integers, but what actually happens is, since 10000 is larger than the current capacity, the capacity is doubled to 20.

Instead of capacity *= 2; perhaps you would want something more along the lines of:

  private void ensureCapacity(int minSize) {
    if(minSize >= capacity) {
      capacity = Math.max(capacity * 2, minSize);
      elements = Arrays.copyOf(elements, capacity);
    }
  }

Initial Capacity

Even without exposing ensureCapacity(int minSize) as a public function, the following test will cause the bug to appear in a different way, causing a ArrayIndexOutOfBounds exception:

  var container = new DynamicArray<Integer>(0);
  container.add(10);

The initial capacity is zero. In attempting to add an item, the length + 1 will exceed the capacity of zero, so the capacity will be doubled from zero to ... zero! Then, elements[length++] = element; will access the first element from an array of length 0. Oops.

You could prevent this with validation in the constructor ...

    if(capacity <= 0)
      throw new IllegalArgumentException("Capacity must be positive");

With the capacity = Math.max(capacity * 2, minSize); fix, this could be relaxed to allow an initial capacity of zero:

    if(capacity < 0)
      throw new IllegalArgumentException("Capacity cannot be negative");

Iteration

You define an Iterator for your DynamicArray, but if the array is modified while your iterator is in flight over the list, odd things may happen.

For example: If you have a DynamicArray<String> containing "foo", "bar" and "baz", you might create the iterator and retrieve the first item: "foo". If you then performed .removeElement(0), the next element returned by the iterator would be "baz", not "bar"!

The standard collections will raise a ConcurrentModificationException in these cases. They achieve this by maintaining a modCount in the container. Each .add() or .remove() operation would increment this by one. When the iterator is created, it captures the current modCount value for the container. On every iterator operation, it checks to see if the modCount has unexpectedly changed, and if so, raise the exception.

Compile time warnings related to generics

You can add @SuppressWarnings("unchecked") annotation to a statement, method, or an entire class. Ideally, you should apply the annotations to the smallest possible scopes to avoid accidentally suppressing warnings you didn't intend to.

See this answer

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I strongly agree to the suggestion to write unittests, But instead of focusing on the code by "writing one test method per public method" we write "one test method per atomic expectation about the units behavior". The difference is, that with the behavior driven approach you have to justify with a test, that a (public) method is needed. \$\endgroup\$ – Timothy Truckle Feb 23 at 18:37
1
\$\begingroup\$
return size() > 0;

Typo, should be (less than or) equal zero.


    for(int i = 0; i < length; i++) {
      elements[i] = null;
    }
    length = 0;

It might be interesting to actually throw the array away and get a clean one in place, for example if this list was previously filled with 100 million entries.


  public boolean add(T element) {
    ensureCapacity(length + 1);
    elements[length++] = element;
    return true;
  }

Given that this can never return false, it might be interesting to return a more meaningful value instead, for example the current instance. That would allow a fluent use when adding multiple values:

dynamicArray
        .add(someObject)
        .add(anotherObject)
        .add(yetAnotherObject);

Your remove accepts null, indexOf does not. Both should accept null, then you can also use indexOf in remove.

  public boolean remove(T element) {
    int index = indexOf(element);
    
    if (index >= 0) {
        removeElement(index);
        
        return true;
    } else {
        return false;
    }
  }

  private void ensureCapacity(int minSize) {
    if(minSize >= capacity) {
      capacity *= 2;
      elements = Arrays.copyOf(elements, capacity);
    }
  }

Depending on the use-case, this might be overkill. Maybe a little bit more flatter, conservative curve might be appropriate.


  private void validateIndexValue(int index) {
    if(index >= length || index < 0) {
      throw new IllegalArgumentException("Bad index value passed : " + index);
    }
  }

Split it into two exception, one for negative values and one for too large values, to make it easier to debug.


You stuck to the conventions already established in the Java world, that's great, so is your naming of things for the most part. I'd rename validateIndexValue to verifyIndex or assertIndex, though, "assert" might yield the wrong message.


As far as I can see, you can infer capacity from the array size.


Overall, looks quite well. Javadoc is missing, you should write one, it's a good exercise and will make you recheck your implementation.

Let's talk API design.

public class DynamicArray<T> implements Iterable<T> {
  private Object[] elements;
  private int length = 0;
  private int capacity = 0;

  public DynamicArray();
  public DynamicArray(int capacity);
  public int size();
  public boolean isEmpty();
  public T get(int index);
  public void set(int index, T element);
  public void clear();
  public boolean add(T element);
  public T removeAt(int index);
  public boolean remove(T element);
  public int indexOf(T element);
  public boolean contains(T element);
  public java.util.Iterator<T> iterator();
  
  private void removeElement(int index);
  private void ensureCapacity(int minSize);
  private void validateIndexValue(int index);
}

Your class is only extensible as far as the public methods go. If I wanted to extend this class and implement a swap method, I will have a hard time doing that. Implementing a different size strategy will basically mean rewriting methods. Now, how could we improve that situation? The easiest is to make the internal properties protected, it's not exactly a neat or fancy solution, but if somebody wants to implement additional methods, they will have all the necessary access.

public class DynamicArray<T> implements Iterable<T> {
  protected Object[] elements;
  protected int length = 0;
  protected int capacity = 0;

  // public SNIP
  
  protected void removeElement(int index);
  protected void ensureCapacity(int minSize);
  protected void validateIndexValue(int index);
}

That gives every extending class the same access as you had, meaning that implementing a swap method or different strategy will be easy to do. But many people will now start ranting about how that is bad design (I disagree on that matter, but let's leave it at that). So we arrive at the question: Can we give an extending class enough access to implement additional functionality, but also protect base functionality? For example, now elements could be null after any call.

We can, we can guard our elements array behind some functions that ensure its well being:

public class DynamicArray<T> implements Iterable<T> {
  private Object[] elements;
  private int length = 0;
  
  protected final Object[] getElements[] {
      return elements;
  }
  
  protected final int getLength() {
      return length;
  }
  
  protected final setElements(Object[] elements, int length) {
      requireNotNull(elements);
      requireZeroOrPositive(length);
      requireLessThan(length, elements.length);
      
      this.elements = elements;
      this.length = length;
  }
  
  protected final setLength(int length) {
      requireZeroOrPositive(length);
      requireLessThan(length, elements.length);
      
      this.length = length;
  }
  
  // SNIP methods as above
}

Neatish, I'd say. This allows us to make fair assumptions about the internal state. It also gives the extending class any freedom to access and modify the array, without the possibility to nulling the reference. Note that modifying the array directly is still possible, and I'd argue that that should stay that way, because the extending class must be able to modify it. Forcing the extending class to retrieve a copy of the array, modify that copy and set it back will do nothing but waste memory and processing power.

With that in place, a swapping method in an extending class can look like this:

public void swap(int firstIndex, int secondIndex) {
    validateIndexValue(firstIndex);
    validateIndexValue(secondIndex);
    
    Object[] elements = getElements();
    
    T firstElement = elements[firstIndex];
    T secondElement = elements[secondIndex];
    
    elements[firstIndex] = secondElement;
    elements[secondIndex] = firstElement;
}

Which is as simple as it can get.

Of course, the internal state can still be "corrupted" to a certain part, by setting a "wrong" length value, but I'd argue that that is the problem of the extending class. After all, the extending class could also override add to perform a division with zero. We can't and should not guard against anything, otherwise you'll have a too restrictive API/class design which will make it impossible to extend your classes. In the real world, that means to either throw out your class, or copy and modify the code of the class.

\$\endgroup\$
2
  • \$\begingroup\$ "return size() > 0;" Typo, should be less than zero. Really? \$\endgroup\$ – Mark Bluemel Feb 23 at 16:20
  • \$\begingroup\$ @MarkBluemel Well, what can I say, was a typo...thanks. \$\endgroup\$ – Bobby Feb 23 at 16:28

Your Answer

devi prasad is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.