Java

TOPIC 24 – DYNAMIC ARRAYS

LESSON NOTE

STATIC LENGTH

By definition, an array has a preset length. We cannot change the length of an array.

An issue arises when we need to increase the size of an array in order to make it hold more information. The solution is to simulate an array that can be resized. This is called a Dynamic Array even if it is built on top of a regular array that cannot be resized. It essentially involves creating a new array of a larger size and copying all the data over to the new array. More on this later.

DYNAMIC ARRAY IN JAVA (ARRAYLIST)

In Java, we have worked with a dynamic array in the ArrayList class. That data structure is built on top of a regular array that needs to change in size.

INSERTING ELEMENTS INTO AN ARRAY

There are a few possible strategies to dealing with the need of having a dynamic array (an array that can change in size).

OPTION 1 – BOUNDED-SIZE ARRAY

When we know the maximum size of our data in advance, we can create an array with that capacity. Of course, we don’t have to use the entire array all the time.

VISUAL EXAMPLE

In the example below, the maximum size of the data (capacity) is 8 while there are only 6 elements in the array at present time.

IMPLEMENTATION

Click here for a simple implementation of a Bounded-Size Array class. Note that to keep it simple, the main was placed inside the same class.

OPTION 2 – RESIZING ARRAY

Another option is to create an entirely new array every time you add or remove an element. This involves having to copy over data from the old array to the new array.

IMPLEMENTATION

Click here for a simple implementation of a Resizing Array class. The main is again inside the class.

COMPARING OPTIONS 1 & 2

The first option is limited because it caps our maximum number of elements to the capacity of the bounded-size array. However, its advantage is that inserting values at the end of the used section of the array can be done very efficiently.

The second option allows us to grow our data to any size we need but is very inefficient as it is constantly copying all the contents of one array to a new one.

OPTION 3 - THE HYBRID APPROACH

A better solution would be to implement a bounded size array that allows for a capacity that changes once it is reached. One suggested approach is to use a bounded-size array but when it is full, then you create a new bounded-size array with double the capacity.

REMOVING ELEMENTS

Removing an element from a dynamic array involves shifting all elements after the one removed up one. Then, one has to deal with the empty element at the end of the array. Either you need to copy all the data to a new correctly-size array or you have to keep track of which part of the array is in use.

LIMITATIONS OF DYNAMIC ARRAYS

All of this work allows us to efficiently insert data at the end of our data. However, no matter how hard we try, adding data at the start or in the middle of a dynamic array remains quite inefficient. Similarly, deleting from a dynamic array is also quite inefficient as we need to shift all data over by one.

HIDDEN DETAILS

The reason for creating a Dynamic Array class is to hide the complexities of the data structure away from the programmer that wants to use it for an application. The programmer only worries about how to use the methods that provide functionality to the data structure.