Home » Core Java » Dynamic Array Java Example

About Venkat-Raman Nagarajan

Venkat-Raman Nagarajan
Venkat works for a major IT firm in India and has more than a decade of experience working and managing Java projects for a banking client.

Dynamic Array Java Example

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.

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.

In this article, we shall discuss the dynamic array and their 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 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 original array to the new one after the allocated space is consumed.

Dynamic Array Java - Adding elements
Fig 1. Adding elements

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.

Dynamic Array Java - Removing element
Fig 2. Removing element

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).

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. Trim operation removes all the unused space.

Dynamic Array Java - Test results
Fig 3. Test results

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.

Download
You can download the full source code of this example here: Dynamic Array Java Example
(+1 rating, 3 votes)
Start the discussion Views Tweet it!

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

 

Leave a Reply

avatar

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
Notify of