Dynamic Array in Java

An array is a fixed-size, homogeneous data structure. The limitation of arrays is that they are fixed in size. It means that we must specify the number of elements while declaring the array. Here, a question arises that what if we want to insert an element and there is no more space left for the new element?

Here, the concept of a dynamic array comes into existence. It expands the size of the array dynamically. Dynamic arrays, also known as ArrayLists. It is a fundamental data structures that provide a flexible way to store and manipulate collections of elements.

What is a dynamic array?

The dynamic array is a variable size list data structure. It grows automatically when we try to insert an element if there is no more space left for the new element. It allows us to add and remove elements. It allocates memory at run time using the heap. It can change its size during run time.

In Java, ArrayList is a resizable implementation. It implements the List interface and provides all methods related to the list operations ArrayLists offer several advantages over traditional arrays, such as automatic resizing, ease of use, and compatibility with generic types. The strength of the dynamic array is:

• Quick lookup
• Variable size
• Cache-friendly

Working of Dynamic Array

In the dynamic array, the elements are stored contiguously from the starting of the array and the remaining space remains unused. We can add the elements until the reserved spaced is completely consumed. When the reserved space is consumed and required to add some elements. In such a case, the fixed-sized array needs to be increased in size. Note that before appending the element, we allocate a bigger array, copy the elements from the array, and return the newly created array.

Another way to add an element is that first, create a function that creates a new array of double size, copies all the elements from the old array, and returns the new array. Similarly, we can also shrink the size of the dynamic array.

Size Vs. Capacity

The initialization of a dynamic array creates a fixed-size array. In the following figure, the array implementation has 10 indices. We have added five elements to the array. Now, the underlying array has a length of five. Therefore, the length of the dynamic array size is 5 and its capacity is 10. The dynamic array keeps track of the endpoint.

Features of Dynamic Array

In Java, the dynamic array has three key features: Add element, delete an element, and resize an array.

Add Element in a Dynamic Array

In the dynamic array, we can create a fixed-size array if we required to add some more elements in the array. Usually, it creates a new array of double size. After that, it copies all the elements to the newly created array. When elements are added to an ArrayList and it reaches its capacity, it automatically expands its internal array to accommodate more elements. We use the following approach:

Delete an Element from a Dynamic Array

If we want to remove an element from the array at the specified index, we use the removeAt(i) method. The method parses the index number of that element which we want to delete. After deleting the element, it shifts the remaining elements (elements that are right to the deleted element) to the left from the specified index number.

We also use the remove() method that deletes an element from the end of the array. After shifting the elements, it stores 0 at the palace of the last element. The remove() method allows us to delete an element at a particular index, while the remove(Object o) method removes the first occurrence of the specified element. Let's understand it through an example, as we have shown in the following figure.

Resizing a Dynamic Array

We need to resize an array in the following two scenarios if:

• The array uses extra memory than required.
• The array occupies all the memory and we need to add elements.

In the first case, we use the srinkSize() method to resize the array. It reduces the size of the array. It free up the extra or unused memory. In the second case, we use the growSize() method to resize the array. It increases the size of the array.

It is an expensive operation because it requires a bigger array and copies all the elements from the previous array after that return the new array.

Suppose in the above array, it is required to add six more elements and, in the array, no more memory is left to store elements. In such cases, we grow the array using the growSize() method.

Iterating Through ArrayLists

We can iterate through the elements of an ArrayList using loops or the enhanced for-loop in Java. Here's an example of iterating through an ArrayList using a traditional for loop:

Initialize a Dynamic Array

The initialization of the dynamic array is the same as the static array. Consider the following Java program that initializes a dynamic array.

Output:

Elements of Array are: 34 90 12 22 9 27

Let's implement the operations in a Java program that we have discussed above.

Output:

Elements of the array:
12 22 35 47 85 26 70 81 96 54 0 0 0 0 0 0 
Size of the array: 16
No. of elements in the array: 10
Elements of the array after adding an element at index 5:
12 22 35 47 85 99 26 70 81 96 54 0 0 0 0 0 Size of the array: 16
No. of elements in the array: 11

Let's shrink the array, delete the last element, and a specified element from the array.

Output:

Elements of the array:
12 22 35 47 85 26 70 81 96 54 0 0 0 0 0 0 Size of the array: 16
No. of elements in the array: 10
Elements of the array after deleting the last element: 12 22 35 47 85 26 70 81 96 0 0 0 0 0 0 0 
Size of the array: 16
No. of elements in the array: 9
Elements of the array after deleting the element at index 7: 12 22 35 47 85 26 70 96 0 0 0 0 0 0 0 0 
Size of the array: 16
No. of elements in the array: 8

Pros of Dynamic Array

• Flexible Size (Resizable at Runtime): In contrast to standard arrays (int[] arr = new int[5];), dynamic arrays expand or contract as the program executes. When you are unsure of how many items will be kept ahead of time, this is useful.

Example: Using ArrayList (Java’s dynamic array)

Output:

Dynamic Array: [10, 20, 30]

• Random Access: Any element can be accessed in constant time (O(1)) by using its index, just like regular arrays.
• Memory Efficient (in some cases): Unlike big static arrays, dynamic arrays do not cause initial memory waste. So, start small and expand as necessary.

Example:

• Integrated with Collections Framework: An element of the Java Collections API is ArrayList. Its built-in functions, such as sort, contains, delete, etc., are very simple to use.
• Better Performance Than LinkedList for Indexing: Since the elements are kept in contiguous memory, accessing an element by index is quicker than using a linked list.

Cons of Dynamic Array

• Costly Resizing (Copy Overhead): Every element that is currently in the array gets duplicated into a new, larger array whenever it reaches its limit. O(n) time is required for this copying.
• Wasted Memory: Often, dynamic arrays grow by a fixed factor (such as 1.5x or 2x) to prevent resizing too frequently. As a result, some RAM is left unused.
• Not Thread-Safe: It is unsafe to utilize ArrayList in multi-threaded systems without adequate locking because it is not synchronized.

Example

• Slow Insert/Delete in Middle: All subsequent elements must be shifted in order to insert or delete in the middle; this is known as O(n) time complexity.

When to use Dynamic Array?

• If the size of an array is unknown or changes frequently.
• If we require frequent insertions at the end because dynamic arrays are optimized for append operations.
• Dynamic array provides fast random-access O(1) using index.
• Instead of creating new arrays manually, dynamic arrays handle resizing internally.
• If you need to frequently loop through elements.
• Dynamic arrays are often used internally for Stack, Queue, and Heap.