Web
Analytics Made Easy - StatCounter

Dynamic Arrays (With Code in C, C++, Java, and Python)

What is a dynamic array?

A dynamic array is a contiguous area of memory whose size grows dynamically as new data is inserted. In static array, we need to specify the size at the time of allocation. If the size of the array is allocated to be 10, we can not insert more than 10 items. However, the dynamic array adjusts it’s size automatically when needed. That means we can store as many items as we want without specifying the size at the time of allocation.

Working of a dynamic array

When we try to insert a new item into the array, we first check if the size is full. If the array is not full, we simply insert the item at the end of the array otherwise we create a new array whose size is double of the current array, we move all the times from old array to new array, we delete the old array to free the memory and finally we insert the item at the end of the expanded array. We start by allocating the array of size 1 and repeat this process when a new item is inserted. Figure 1 shows the insertion process for the first 9 items.

Fig 1: Illustrating dynamic array

Complexity

We do amortized analysis to find the complexity of the insertion operation (insertion at the end of the array). The normal insertion (when the array is not full) takes the constant time but when the array is full, we need to perform extra work of moving the items into the new array and it takes O(n) time. Since we occasionally do the O(n) operation, the average time of the insertion operation is O(1). Please refer to this link to get the idea of amortized complexity.

Implementation

Most of the programming languages already have the implementation for dynamic arrays. ArrayList in Java, vector in C++, list in Python is an example of a dynamic array. I have implemented a dynamic array in C++ and JAVA which is given below.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// C++ implementation of Dynamic Array
#include <iostream>
using namespace std;

template <class T>
class DynamicArray {
private:
T *list;
int max_size;
int length;
public:
DynamicArray() {
// initially allocate a single memory block
max_size = 1;
list = new T[max_size];
length = 0;
}

// insert a new item to the end of the list
void add(T item) {
if (isFull()) {
// create temporary list with double size
max_size = 2 * max_size;
T *temp_list = new T[2* max_size];

// move all the elements to the temporary list
for (int i = 0; i < length; i++) {
temp_list[i] = list[i];
}

// delete the old list
delete [] list;

// rename temp list
list = temp_list;
}

// add the new item at the end of the list
list[length] = item;
length++;
}

void printList() {
for (int i = 0; i < length; i++) {
cout<<list[i]<<' ';
}
cout<<endl;
}

// check if the list is full
bool isFull() {
return length == max_size;
}

~DynamicArray() {
delete [] list;
}


};

int main() {
DynamicArray<char> list;
list.add('1');
list.add('2');
list.add('3');
list.add('4');
list.add('5');
list.add('6');
list.add('7');
list.add('8');
list.add('9');
list.printList();
return 0;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 // Java implementation of Dynamic Array
class DynamicArray {
private int [] list;
private int max_size;
private int length;

public DynamicArray() {
// initially allocate a single memory block
max_size = 1;
list = new int[max_size];
length = 0;
}

// insert new item to the end of the list
public void add(int item) {
if (isFull()) {
// create temporary list with double size
max_size = 2 * max_size;
int [] temp_list = new int[2* max_size];

// move all the elements to the temporary list
for (int i = 0; i < length; i++) {
temp_list[i] = list[i];
}

// rename temp list
list = temp_list;
}

// add the new item at the end of the list
list[length] = item;
length++;
}

public void printList() {
for (int i = 0; i < length; i++) {
System.out.print(list[i] + " ");
}
System.out.println();
}

// check if the list is full
boolean isFull() {
return length == max_size;
}

public static void main(String [] args) {
DynamicArray list = new DynamicArray();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.printList();
}
}