An Array is a container object that holds a fixed number of values of a single type. The length of an array is established when the array is created. The length is fixed after creation. In this article, we will show Java dynamic arrays.
A dynamic array is a variable-size list data structure that allows elements to be added or removed. Dynamic arrays overcome a limit of static arrays, which have a fixed capacity that needs to be specified at allocation.
Let’s now discuss the dynamic array and its implementations in Java (Vector, ArrayList, LinkedList, CopyOnWriteArrayList).
1. Dynamic array
A simple dynamic array can be constructed by allocating an array of fixed size, typically larger than the number of elements immediately required. The elements of the dynamic array are stored at the start of the underlying array, and the remaining positions towards the end of the array are reserved or unused. Elements can be added at the end of the dynamic array by using reserved space until the space is completely consumed. The underlying fixed-size array needs to be increased in size when further elements have to be added after all the space is consumed. Typically resizing is expensive as it involves allocating a new array and copying each element from the original array (costs O(n) time).
A fixed-size array will suffice in scenarios where the maximum logical size is fixed. A dynamic array will be needed when the maximum logical size is unknown initially, or likely to change.
2. Features of Dynamic Array
Key features of a dynamic array are adding, deleting, and resizing an element. Let us now check these features.
2.1 Add an element to a dynamic array
As discussed in the previous section, elements are added at the end of an array. A new array (typically double the original array size) is created and data is copied from the original array to the new one after the allocated space is consumed.
2.2 Delete an element from a dynamic array
The remove(i) removes the element at index location – ‘i’ and shifts all the elements at the right side of the index to left.
2.3 Resize an array
An array’s size can be increased or decreased. Resizing is usually an expensive operation, as it would mean creating a new array and copying all the elements (costs O(n) time).
2.4 Table for complexity O(n)
A dynamic array automatically grows when you try to make insertion and there is no more space left for the new item. Usually, the array doubles in size. In this case, a new array has to be created with double the size of the previous one and copy all the elements to the new one. This will take O(n), but a simple insertion on an empty cell costs only O(1). This is also true when we are trying to remove an element.
Also if we want to search the array, giving the index takes only O(1). If we search by the value we have to parse all the array so the worst-case scenario is O(n).
| Operations | average | worst |
| access | O(1) | O(1) |
| search | O(n) | O(n) |
| insertion | O(1) | O(n) |
| deletion | O(1) | O(n) |
3. Dynamic array Java example
Let us now look at an example with the features discussed above. DynamicArray class provides operations to add and remove items from an array.
DynamicArray.java
import java.util.Arrays;
public class DynamicArray{
private int array[];
// holds the current size of array
private int size;
// holds the total capacity of array
private int capacity;
// default constructor to initialize the array and values
public DynamicArray(){
array = new int[2];
size=0;
capacity=2;
}
// to add an element at the end
public void addElement(int element){
// double the capacity if all the allocated space is utilized
if (size == capacity){
ensureCapacity(2);
}
array[size] = element;
size++;
}
// to add an element at a particular index
public void addElement(int index, int element){
// double the capacity if all the allocated space is utilized
if (size == capacity){
ensureCapacity(2);
}
// shift all elements from the given index to right
for(int i=size-1;i>=index;i--){
array[i+1] = array[i];
}
// insert the element at the specified index
array[index] = element;
size++;
}
// to get an element at an index
public int getElement(int index){
return array[index];
}
// to remove an element at a particular index
public void remove(int index){
if(index>=size || index<0){
System.out.println("No element at this index");
}else{
for(int i=index;i<size-1;i++){
array[i] = array[i+1];
}
array[size-1]=0;
size--;
}
}
/* method to increase the capacity, if necessary, to ensure it can hold at least the
* number of elements specified by minimum capacity arguement
*/
public void ensureCapacity(int minCapacity){
int temp[] = new int[capacity*minCapacity];
for (int i=0; i < capacity; i++){
temp[i] = array[i];
}
array = temp;
capacity = capacity * minCapacity;
}
/*
* Trim the capacity of dynamic array to the current size. i.e. remove unused space
*/
public void trimToSize(){
System.out.println("Trimming the array");
int temp[] = new int[size];
for (int i=0; i < size; i++){
temp[i] = array[i];
}
array = temp;
capacity = array.length;
}
// to get the current size
public int size(){
return size;
}
// to get the current capacity
public int capacity(){
return capacity;
}
// method to print elements in array
public void printElements(){
System.out.println("elements in array are :"+Arrays.toString(array));
}
}
DynamicArrayTest class has instructions to add and remove elements.
DynamicArrayTest.java
public class DynamicArrayTest{
public static void main(String args[]){
DynamicArray array = new DynamicArray();
// adding elements at index 0 and 1
array.addElement(1);
array.addElement(2);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.addElement(3);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
// add element at index 1
array.addElement(1,5);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
// add element at index 2
array.addElement(2,6);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
array.remove(2);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
array.remove(2);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
array.remove(1);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
array.remove(2);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
array.remove(1);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
// Trim the array
array.trimToSize();
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
array.addElement(2);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
array.addElement(3);
System.out.println("Size :"+array.size()+
" and Capacity :"+array.capacity());
array.printElements();
}
}
Compile and execute the test class. The result would be as shown below. Note how the capacity increases after the allocated space is utilized. The trim operation removes all the unused space.
4. Built-in Dynamic arrays in Java
Java has built-in dynamic arrays. These are Vector, ArrayList, LinkedList and CopyOnWriteArrayList.
ArrayList is a resizable array implementation of the List interface. It implements all optional list operations and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. Note that this implementation is not synchronized.
The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. The size of a Vector can grow or shrink as needed to accommodate adding or removing items after Vector has been created. Unlike the new collection implementations, Vector is synchronized. if a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.
The LinkedList is a doubly-linked list implementation of the List and Deque interfaces. It implements all optional list operations and permits all elements (including null). Note that this implementation is not synchronized.
The CopyOnWriteArrayList is a thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array. This is costly, but more efficient when traversals operations vastly outnumber mutations. All elements (including null) are permitted. The snapshot style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, and hence interference is impossible.
5. Download the source code
This was an example for Dynamic arrays.
You can download the full source code of this example here: Dynamic Array Java Example
Last updated on Oct. 14th, 2021
Helped me a lot and well explained. Thank you.