Dynamic Array

Description

A dynamic array is an array data structure that can grow and shrink in size dynamically as elements are added or removed.

It provides constant time access and amortized constant insertion/deletion at end.

A dynamic array doubles its capacity when full and halves when very sparse to maintain optimal size.

This provides the flexibility of vectors with the performance of arrays. It adapts space efficiently for changing storage needs.

Solution

Here is a simple dynamic array implementation:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class DynamicArray {
  private int[] arr;
  private int capacity = 0;
  private int size = 0;

  public DynamicArray() {
    capacity = 1;
    arr = new int[capacity]; 
  }

  public void add(int num) {
    if (size + 1 > capacity) {
      grow();
    }
    arr[size++] = num;
  }

  private void grow() {
    capacity *= 2;
    int[] newarr = new int[capacity];

    for(int i=0; i<size; i++) {
      newarr[i] = arr[i];
    }
    arr = newarr;
  } 
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class DynamicArray {
  int *arr;
  int capacity;
  int size;

public:
  DynamicArray() {
    capacity = 1;
    arr = new int[capacity];
    size = 0;
  }

  void add(int num) {
    if (size + 1 > capacity) {
      grow();
    }
    arr[size++] = num;
  }

private:
  void grow() {
    capacity *= 2;
    int *newarr = new int[capacity];
    
    for(int i=0; i<size; i++) {
      newarr[i] = arr[i]; 
    }
    delete[] arr;
    arr = newarr;
  }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class DynamicArray:

  def __init__(self):
    self.n = 0 
    self.capacity = 1
    self.A = self.make_array(self.capacity)

  def __len__(self):
    return self.n
  
  def __getitem__(self,k):
    if not 0 <= k <self.n:
      return IndexError('K is out of bounds!') 
    return self.A[k]  

  def append(self, ele):
    if self.n == self.capacity:
      self._resize(2*self.capacity)    
    self.A[self.n] = ele
    self.n += 1

  def _resize(self, new_cap):
    B = self.make_array(new_cap)
    for k in range(self.n):
      B[k] = self.A[k]
    self.A = B
    self.capacity = new_cap

  def make_array(self, new_cap):
    return (new_cap * ctypes.py_object)()

This dynamically resizes the underlying array as needed for changing storage requirements.

Description: Dynamic Array

A dynamic array is a data structure that allocates memory for elements in a contiguous block. Unlike a static array, it can automatically resize itself when the number of elements exceeds its current capacity. Typically, the capacity is doubled when resizing occurs. Dynamic arrays provide constant-time access to elements and are efficient for many scenarios, although appending elements may occasionally take longer due to the resizing process.

Solution:

Below are implementations that demonstrate the concept of a dynamic array in Java, C++, and Python.

Java

In Java, dynamic arrays are provided through the ArrayList class. Here’s a simplified example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import java.util.ArrayList;

public class DynamicArrayExample {
    public static void main(String[] args) {
        ArrayList<Integer> dynamicArray = new ArrayList<>();

        dynamicArray.add(1);
        dynamicArray.add(2);
        dynamicArray.add(3);

        System.out.println("Element at index 1: " + dynamicArray.get(1));
    }
}

C++

In C++, the Standard Template Library (STL) offers dynamic arrays through the vector class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <iostream>
#include <vector>

int main() {
    std::vector<int> dynamicArray;

    dynamicArray.push_back(1);
    dynamicArray.push_back(2);
    dynamicArray.push_back(3);

    std::cout << "Element at index 1: " << dynamicArray[1] << std::endl;
    return 0;
}

Python

Python’s list data type is an implementation of a dynamic array:

1
2
3
4
5
6
7
dynamic_array = []

dynamic_array.append(1)
dynamic_array.append(2)
dynamic_array.append(3)

print("Element at index 1:", dynamic_array[1])

Key Takeaways:

Dynamic arrays automatically resize themselves, usually doubling their capacity when full.
They provide constant-time access for indexed elements.
Java’s ArrayList, C++’s vector, and Python’s list are common implementations of dynamic arrays.
Even though dynamic arrays may seem to insert elements in constant time, occasional resizing might make it linear (O(n)) for that specific insertion.

Knowing how dynamic arrays work is foundational for understanding more complex data structures and for efficient problem-solving in coding interviews.