Dynamic arrays
One of the problems occurring when working with array data structure is that its size can not be changed during program run. There is no straight forward solution, but we can encapsulate capacity management.
Internal representation
The idea is simple. Application allocates some amount of memory and logically divides it into two parts. One part contains the data and another one is a free space. Initially all allocated space is free. During the data structure functioning, the boundary between used / free parts changes. If there no more free space to use, storage is expanded by creating new array of larger size and copying old contents to the new location. Dynamic array data structure has following fields:
- storage: dynamically allocated space to store data;
- capacity value: size of the storage;
- size value: size of the real data.
Functions
Code snippets
Java
There is no need to store capacity in Java. Use storage.length to get it.
public class DynamicArray {
private int[] storage;
private int size;
public DynamicArray() {
storage = new int[10];
size = 0;
}
public DynamicArray(int capacity) {
storage = new int[capacity];
size = 0;
}
}
C++
class DynamicArray {
private:
int size;
int capacity;
int *storage;
public:
DynamicArray() {
capacity = 10;
size = 0;
storage = new int[capacity];
}
DynamicArray(int capacity) {
this->capacity = capacity;
size = 0;
storage = new int[capacity];
}
~DynamicArray() {
delete[] storage;
}
};
|