1. Overview
In this tutorial, we’ll briefly look at the similarities and dissimilarities in memory allocation between Java arrays and the standard ArrayList. Furthermore, we’ll see how to append and insert elements in an array and ArrayList.
2. Java Arrays and ArrayList
A Java array is a basic data structure provided by the language. In contrast, ArrayList is an implementation of the List interface backed by an array and is provided in the Java Collections Framework.
2.1. Accessing and Modifying Elements
We can access and modify array elements using the square brackets notation:
System.out.println(anArray[1]);
anArray[1] = 4;
On the other hand, ArrayList has a set of methods to access and modify elements:
int n = anArrayList.get(1);
anArrayList.set(1, 4);
2.2. Fixed vs Dynamic Size
An array and the ArrayList both allocate heap memory in a similar manner, but what differs is that an array is fixed-sized, while the size of an ArrayList increases dynamically.
Since a Java array is fixed-sized, we need to provide the size while instantiating it. It is not possible to increase the size of the array once it has been instantiated. Instead, we need to create a new array with the adjusted size and copy all the elements from the previous array.
ArrayList is a resizable array implementation of the List interface — that is, ArrayList grows dynamically as elements are added to it. When the number of current elements (including the new element to be added to the ArrayList) is greater than the maximum size of its underlying array, then the ArrayList increases the size of the underlying array.
The growth strategy for the underlying array depends on the implementation of the ArrayList. However, since the size of the underlying array cannot be increased dynamically, a new array is created and the old array elements are copied into the new array.
The add operation has a constant amortized time cost. In other words, adding n elements to an ArrayList requires O(n) time.
2.3. Element Types
An array can contain primitive as well as non-primitive data types, depending on the definition of the array. However, an ArrayList can only contain non-primitive data types.
When we insert elements with primitive data types into an ArrayList, the Java compiler automatically converts the primitive data type into its corresponding object wrapper class.
Let’s now look at how to append and insert elements in Java arrays and the ArrayList.
3. Appending an Element
As we’ve already seen, arrays are of fixed size.
So, to append an element, first, we need to declare a new array that is larger than the old array and copy the elements from the old array to the newly created array. After that, we can append the new element to this newly created array.
Let’s look at its implementation in Java without using any utility classes:
public Integer[] addElementUsingPureJava(Integer[] srcArray, int elementToAdd) {
Integer[] destArray = new Integer[srcArray.length+1];
for(int i = 0; i < srcArray.length; i++) {
destArray[i] = srcArray[i];
}
destArray[destArray.length - 1] = elementToAdd;
return destArray;
}
Alternately, the Arrays class provides a utility method copyOf(), which assists in creating a new array of larger size and copying all the elements from the old array:
int[] destArray = Arrays.copyOf(srcArray, srcArray.length + 1);
Once we have created a new array, we can easily append the new element to the array:
destArray[destArray.length - 1] = elementToAdd;
On the other hand, appending an element in ArrayList is quite easy:
anArrayList.add(newElement);
4. Inserting an Element at Index
Inserting an element at a given index without losing the previously added elements is not a simple task in arrays.
First of all, if the array already contains the number of elements equal to its size, then we first need to create a new array with a larger size and copy the elements over to the new array.
Furthermore, we need to shift all elements that come after the specified index by one position to the right:
public static int[] insertAnElementAtAGivenIndex(final int[] srcArray, int index, int newElement) {
int[] destArray = new int[srcArray.length+1];
int j = 0;
for(int i = 0; i < destArray.length; i++) {
if(i == index) {
destArray[i] = newElement;
} else {
destArray[i] = srcArray[j];
j++;
}
}
return destArray;
}
Next, let’s create a test to verify if this method works as expected:
int[] expectedArray = { 1, 2, 42, 3, 4 };
int[] anArray = { 1, 2, 3, 4 };
int[] outputArray = ArrayOperations.insertAnElementAtAGivenIndex(anArray, 2, 42);
assertThat(outputArray).containsExactly(expectedArray);
The ArrayUtils class from the popular Apache Commons Lang 3 library gives us a simpler solution to insert items into an array:
int[] destArray = ArrayUtils.insert(2, srcArray, 77);
We have to specify the index at which we want to insert the value, the source array, and the value to insert.
The insert() method returns a new array containing a larger number of elements, with the new element at the specified index and all remaining elements shifted one position to the right.
Note that the last argument of the insert() method is a variable argument, so we can insert any number of items into an array.
Let’s use it to insert three elements in srcArray starting at index two:
int[] destArray = ArrayUtils.insert(2, srcArray, 77, 88, 99);
And the remaining elements will be shifted three places to the right.
Furthermore, this can be achieved trivially for the ArrayList:
anArrayList.add(index, newElement);
ArrayList shifts the elements and inserts the element at the required location.
5. Prepending an Element
By prepending an element to an array, we aim to insert an element at the index 0. Of course, we can solve the problem using our insertAnElementAtAGivenIndex() method:
int[] anArray = { 1, 2, 3, 4 };
int[] expectedArray = { 42, 1, 2, 3, 4 };
int[] result = ArrayOperations.insertAnElementAtAGivenIndex(anArray, 0, 42);
assertThat(result).containsExactly(expectedArray);
Alternatively, we can use the System.arraycopy() method to avoid the shifting operations:
public static int[] prependAnElementToArray(int[] srcArray, int element) {
int[] newArray = new int[srcArray.length + 1];
newArray[0] = element;
System.arraycopy(srcArray, 0, newArray, 1, srcArray.length);
return newArray;
}
Next, let’s test this method using the same input:
int[] anArray = { 1, 2, 3, 4 };
int[] expectedArray = { 42, 1, 2, 3, 4 };
int[] result = ArrayOperations.prependAnElementToArray(anArray, 42);
assertThat(result).containsExactly(expectedArray);
Additionally, the ArrayUtils.addFirst() method from Apache Commons Lang 3 can solve the problem straightforwardly:
int[] anArray = { 1, 2, 3, 4 };
int[] expectedArray = { 42, 1, 2, 3, 4 };
int[] result = ArrayUtils.addFirst(anArray, 42);
assertThat(result).containsExactly(expectedArray);
It’s worth noting that if the given array isn’t null, ArrayUtils.addFirst() internally invokes ArrayUtils.insert() to insert the desired element at index 0.
Conversely, if we want to add an element to an ArrayList, we can still use the ArrayList.add() method and pass 0 as the index: anArrayList.add(0, newElement).
6. Conclusion
In this article, we looked at Java array and ArrayList. Furthermore, we looked at the similarities and differences between the two. Finally, we saw how to append and insert elements in an array and ArrayList.
As always, the full source code of the working examples is available over on GitHub.