A Dynamic Array is an array data structure that automatically resizes itself when it reaches capacity.
Unlike static arrays, which have a fixed size, dynamic arrays can grow or shrink as needed.
Why Use Dynamic Arrays?
- Dynamic Sizing: No need to specify the size of the array in advance.
- Ease of Use: Simplifies coding by automatically handling resizing.
- Performance: Offers constant-time access to elements and efficient use of memory.
- Widespread Usage: Used in building other data structures like stacks, queues, and hash tables.
Java Implementation
Here is a simple implementation of a dynamic array in Java:
public class DynamicArray<T> {
private Object[] array;
private int size;
private int capacity;
public DynamicArray() {
this.capacity = 1;
this.size = 0;
this.array = new Object[capacity];
}
public T get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
return (T) array[index];
}
public void add(T element) {
if (size == capacity) {
resize(2 * capacity);
}
array[size] = element;
size++;
}
public void remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
array[index] = null;
System.arraycopy(array, index + 1, array, index, size - index - 1);
size--;
if (size <= capacity / 4) {
resize(capacity / 2);
}
}
private void resize(int newCapacity) {
Object[] newArray = new Object[newCapacity];
System.arraycopy(array, 0, newArray, 0, size);
array = newArray;
capacity = newCapacity;
}
public int size() {
return size;
}
public static void main(String[] args) {
DynamicArray<Integer> dynamicArray = new DynamicArray<>();
dynamicArray.add(1);
dynamicArray.add(2);
dynamicArray.add(3);
System.out.println("Element at index 1: " + dynamicArray.get(1)); // Output: Element at index 1: 2
System.out.println("Array size: " + dynamicArray.size()); // Output: Array size: 3
dynamicArray.remove(1);
System.out.println("Array size after removal: " + dynamicArray.size()); // Output: Array size after removal: 2
}
}
Dynamic arrays are versatile and easy to use, offering automatic resizing and efficient memory usage. They are especially useful in scenarios where you need a flexible-size array without worrying about its limitations.
The Java Collections Framework provides built-in dynamic arrays like ArrayList
, but understanding how to implement one from scratch is a great exercise for mastering the underlying logic and performance considerations.
Below is a simple Java code snippet that demonstrates basic operations you can perform using Java’s built-in ArrayList
class.
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
// Initialize an empty ArrayList
ArrayList<Integer> numbers = new ArrayList<>();
// Add elements
numbers.add(1);
numbers.add(2);
numbers.add(3);
// Display elements
System.out.println("ArrayList elements: " + numbers); // Output: [1, 2, 3]
// Access element by index
int elementAtIndex1 = numbers.get(1);
System.out.println("Element at index 1: " + elementAtIndex1); // Output: 2
// Remove element by index
numbers.remove(1);
// Display elements after removal
System.out.println("ArrayList after removal: " + numbers); // Output: [1, 3]
// Get the size of the ArrayList
int size = numbers.size();
System.out.println("Size of ArrayList: " + size); // Output: 2
}
}