Dynamic Array in Java

Introduction to Dynamic Array in Java

We all are familiar with Array data structure. It is one of the most commonly used data structures in all programming languages.

Arrays are:

• linear (store elements in a sequential order),
• homogeneous (can store elements of the same type) and
• contiguous (allocate consecutive blocks of memory to the elements)

data structures. Arrays have a fixed size and it has to be specified at the time of creation. This causes a menace when we want to add elements beyond its initial size at runtime.

In this scenario, we have to create a new array with a bigger size and copy the elements of the previous array to the newly created array. This not just wastes time, but also wastes a lot of memory.

Solution

In order to mitigate the sizing problem of the array, dynamic arrays came into the picture. ArrayList data structure is used to implement the concept of dynamic data structures in Java. As the name suggests, dynamic arrays have a dynamic size modifiable at runtime. We do not have to specify the size of the ArrayList at the time of creation.

Advantages of Dynamic Arrays:

• Variable size: We do not need to specify the initial size, it is variable in nature according to the elements inserted or deleted.
• Constant look-up time: When the element has to be retrieved at a given index, ArrayList takes O(1) time same as conventional arrays.
• Cache friendly: Dynamic arrays also put elements in a contiguous manner which results in an efficient cache utilization.

Disadvantage of Dynamic Arrays:

O(N) time complexity: The worst case time complexity of adding an element to an ArrayList data structure is $O(N)$ when a new array has to be created and all the elements copied to it.

Working of Dynamic Array in Java

The default capacity of dynamic arrays in Java is 10. That means internally, a dynamic array with an internal capacity 10 is created. Whenever a user inserts an element in the dynamic array, its size increases.

When the size of the dynamic array becomes equal to its capacity, a new array with double the capacity gets created and the previous elements are stored inside the new array created internally.

Size vs. Capacity

Capacity is the current maximum number of elements a dynamic array can hold, whereas Size is the total elements present in the dynamic array.

In the example, above the array can solve a maximum of 9 elements. However, currently it holds 6 elements. Hence, it has a capacity of 9 and size of 6.

Creating a Dynamic Array in Java

Syntax of ArrayList Declaration:

Using this, we can create an ArrayList of that specific data type whose initial capacity is 10.

Example:

Output:

Explanation:

We have created a dynamic array i.e., an ArrayList of integers arr and then checked its size. Since the ArrayList has no elements added, its size is 0 at present. When the elements are added, their size increases.

Add Element in a Dynamic Array

To add an element in a dynamic array, we use the add() function.

Syntax:

To add an Integer elem to the ArrayList arr declared above, we can use the following statement:

Example-

Output-

Explanation:

We have created an ArrayList i.e., a dynamic array and added elements to it. We can see that after the elements are added, the size of the dynamic array increases.

Resizing a Dynamic Array in Java

As discussed before, when dynamic arrays are created, its internal implementation uses an array. So, at a point when the size of the dynamic array becomes equal to its capacity, a new array with a double size is created.

This is a snippet showing the internal resizing:

Dynamic Array with ArrayList

Now we will see an example where we can perform some operations on the dynamic array.

Example-

Output-

Explanation:

We have created a dynamic array i.e. ArrayList arr and we have performed several operations like adding, removing and getting an element.