Static vs Dynamic Arrays
A static array represents a contiguous block of memory where elements are accessed via integer indices. It serves as the fundamental data structure at the hardware level. Dynamic arrays, conversely, are abstractions built atop static arrays provided by high-level languages. They encapsulate standard operations like insertion, deletion, and automatic memory resizing, shielding developers from manual memory management.
Static Array Initialization and Memory Layout
Declaring a static array allocates a fixed contiguous memory segment. For instance, initializing an integer array of capacity 10 reserves 40 bytes (10 elements × 4 bytes per integer). The array variable itself holds the base address of this memory block.
public class ArrayBasics {
public static void main(String[] args) {
// Allocates 40 bytes of contiguous memory
int[] data = new int[10];
// Index-based assignment
data[0] = 5;
data[1] = 12;
// Index-based retrieval
int val = data[0];
}
}Given the base address, element size, and index, the memory address of any element is calculated instantly. This grants static arrays the capability of O(1) random access, as memory address computation takes constant time.
Insertion Operations
Appending at the End
Adding an element to the first available slot at the end of the occupied section requires only a single index assignment, resulting in O(1) time complexity.
public class AppendDemo {
public static void main(String[] args) {
int[] data = new int[10];
// Populate first 4 slots
for (int i = 0; i < 4; i++) {
data[i] = i * 2;
}
// Append new elements
data[4] = 8;
data[5] = 10;
}
}Inserting in the Middle
To insert an element at a specific index, all subsequent elements must shift one position to the right to vacate the target slot. This shifting process imposes an O(N) time complexity.
public class InsertMiddle {
public static void main(String[] args) {
int[] data = new int[10];
for (int i = 0; i < 4; i++) {
data[i] = i * 2;
}
// Insert 99 at index 2
// Shift elements from right to left to avoid overwriting
for (int i = 4; i > 2; i--) {
data[i] = data[i - 1];
}
data[2] = 99;
}
}Expanding Capacity
Static memory blocks cannot expand in-place because adjacent memory might be occupied. When the array reaches its limit, expansion requires allocating a larger memory block, copying existing elements, and appending the new one. This O(N) process is called resizing.
public class ResizeDemo {
public static void main(String[] args) {
int[] data = new int[10];
for (int i = 0; i < 10; i++) {
data[i] = i;
}
// Need to add an 11th element
int[] expanded = new int[20];
for (int i = 0; i < 10; i++) {
expanded[i] = data[i];
}
expanded[10] = 10;
}
}Deletion Operations
Removing from the End
Deleting the last element simply involves logical removal, often marking it with a sentinel value or decrementing a length counter. This operates in O(1) time.
public class DeleteEnd {
public static void main(String[] args) {
int[] data = new int[10];
for (int i = 0; i < 5; i++) {
data[i] = i;
}
// Mark the last slot as vacant
data[4] = 0;
}
}Removing from the Middle
When removing an element from the interior, all elements following it must shift left by one position to fill the gap. This data migration results in O(N) time complexity.
public class DeleteMiddle {
public static void main(String[] args) {
int[] data = new int[10];
for (int i = 0; i < 5; i++) {
data[i] = i;
}
// Remove element at index 1
for (int i = 1; i < 4; i++) {
data[i] = data[i + 1];
}
data[4] = 0;
}
}Read and Update
Both reading a value at a given index and updating a value at a given index leverage direct memory access, achieving O(1) time complexity.
Dynamic Arrays
Dynamic arrays abstract the underlying static array, handling automatic resizing and offering a suite of built-in methods for manipulation.
import java.util.ArrayList;
public class DynamicArrayDemo {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
// Append (O(1))
for (int i = 0; i < 10; i++) {
list.add(i);
}
// Insert at index (O(N))
list.add(2, 999);
// Insert at head (O(N))
list.add(0, -5);
// Remove last (O(1))
list.remove(list.size() - 1);
// Remove at index (O(N))
list.remove(2);
// Access by index (O(1))
int element = list.get(0);
// Modify by index (O(1))
list.set(0, 100);
// Find index by value (O(N))
int pos = list.indexOf(999);
}
}Circular Arrays
A standard linear array can be treated as a circle logically by wrapping indices using modular arithmetic. When the index reaches the end, it wraps back to the beginning.
public class CircularTraversal {
public static void main(String[] args) {
int[] data = {10, 20, 30, 40, 50};
int idx = 0;
while (true) {
System.out.println(data[idx]);
idx = (idx + 1) % data.length; // Wraps around
}
}
}Head and Tail Pointers
A circular array typically maintains two pointers: head (pointing to the first valid element) and tail (pointing to the position immediately after the last valid element). This forms a left-closed, right-open interval [head, tail). When pointers cross array boundaries, they wrap around using modulo operations, enabling O(1) insertions and deletions at both ends.
Generic Circular Array Implementation
public class RingBuffer<T> {
private T[] buffer;
private int head;
private int tail;
private int len;
private int capacity;
public RingBuffer() {
this(1);
}
@SuppressWarnings("unchecked")
public RingBuffer(int initialCapacity) {
this.capacity = initialCapacity;
this.buffer = (T[]) new Object[initialCapacity];
this.head = 0;
this.tail = 0;
this.len = 0;
}
@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
T[] newBuffer = (T[]) new Object[newCapacity];
for (int i = 0; i < len; i++) {
newBuffer[i] = buffer[(head + i) % capacity];
}
buffer = newBuffer;
head = 0;
tail = len;
capacity = newCapacity;
}
public void pushFront(T value) {
if (isFull()) {
resize(capacity * 2);
}
head = (head - 1 + capacity) % capacity;
buffer[head] = value;
len++;
}
public T popFront() {
if (isEmpty()) {
throw new IllegalStateException("Buffer is empty");
}
T value = buffer[head];
buffer[head] = null;
head = (head + 1) % capacity;
len--;
if (len > 0 && len == capacity / 4) {
resize(capacity / 2);
}
return value;
}
public void pushBack(T value) {
if (isFull()) {
resize(capacity * 2);
}
buffer[tail] = value;
tail = (tail + 1) % capacity;
len++;
}
public T popBack() {
if (isEmpty()) {
throw new IllegalStateException("Buffer is empty");
}
tail = (tail - 1 + capacity) % capacity;
T value = buffer[tail];
buffer[tail] = null;
len--;
if (len > 0 && len == capacity / 4) {
resize(capacity / 2);
}
return value;
}
public T peekFront() {
if (isEmpty()) {
throw new IllegalStateException("Buffer is empty");
}
return buffer[head];
}
public T peekBack() {
if (isEmpty()) {
throw new IllegalStateException("Buffer is empty");
}
return buffer[(tail - 1 + capacity) % capacity];
}
public boolean isFull() {
return len == capacity;
}
public boolean isEmpty() {
return len == 0;
}
public int size() {
return len;
}
}