Card 06/ 09
Dynamic Array in Python, Java and TypeScript
A minimal growable array, then the built-in each language provides.
A dynamic array is a fixed array plus a count of the elements it holds and a rule for growing. This card covers a minimal one in Python, Java and TypeScript, with append, get and insert at an index, and then the built-in each language provides for the same job.
Each listing keeps the size apart from the capacity, which is the length of the fixed array underneath. append is an insert at the end. insert checks the index, grows the array if it is full, shifts the elements from the index onwards one cell right, and writes the new value. The resize step reserves twice the capacity, copies every element and prints the new capacity with the copies made in total. The last lines do the same work with the built-in.
Before the output: after appending 1 to 9 and inserting 0 at index 0, which capacities does the array print, and how many copies in total?
Capacities 2, 4, 8 and 16, with 15 copies in total. Inserting 0 needs no resize, because nine elements leave room in 16 cells.
The highlighted lines are the full check, the shift and the copy.
A doubling dynamic array, then the built-in
class DynamicArray:
def __init__(self) -> None:
self.capacity = 1
self.size = 0
self.cells: list[int] = [0] * self.capacity
self.copies = 0
def append(self, value: int) -> None:
self.insert(self.size, value)
def get(self, index: int) -> int:
if not 0 <= index < self.size:
raise IndexError(index)
return self.cells[index]
def insert(self, index: int, value: int) -> None:
if not 0 <= index <= self.size:
raise IndexError(index)
if self.size == self.capacity:
self._resize(self.capacity * 2)
for i in range(self.size, index, -1):
self.cells[i] = self.cells[i - 1]
self.cells[index] = value
self.size += 1
def _resize(self, new_capacity: int) -> None:
bigger = [0] * new_capacity
for i in range(self.size):
bigger[i] = self.cells[i]
self.copies += 1
self.cells = bigger
self.capacity = new_capacity
print(f"capacity {new_capacity}, copies in total {self.copies}")
numbers = DynamicArray()
for value in range(1, 10):
numbers.append(value)
numbers.insert(0, 0)
print(f"size {numbers.size}, first {numbers.get(0)}, last {numbers.get(numbers.size - 1)}")
built_in = list(range(1, 10))
built_in.insert(0, 0)
print(built_in)capacity 2, copies in total 1
capacity 4, copies in total 3
capacity 8, copies in total 7
capacity 16, copies in total 15
size 10, first 0, last 9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]import java.util.ArrayList;
import java.util.List;
public class DynamicArray {
private int[] cells = new int[1];
private int size = 0;
private int copies = 0;
void append(int value) {
insert(size, value);
}
int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(index);
}
return cells[index];
}
void insert(int index, int value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(index);
}
if (size == cells.length) {
resize(cells.length * 2);
}
for (int i = size; i > index; i--) {
cells[i] = cells[i - 1];
}
cells[index] = value;
size++;
}
private void resize(int newCapacity) {
int[] bigger = new int[newCapacity];
for (int i = 0; i < size; i++) {
bigger[i] = cells[i];
copies++;
}
cells = bigger;
System.out.println("capacity " + newCapacity + ", copies in total " + copies);
}
public static void main(String[] args) {
DynamicArray numbers = new DynamicArray();
for (int value = 1; value <= 9; value++) {
numbers.append(value);
}
numbers.insert(0, 0);
System.out.println("size " + numbers.size + ", first " + numbers.get(0) + ", last " + numbers.get(numbers.size - 1));
List<Integer> builtIn = new ArrayList<>();
for (int value = 1; value <= 9; value++) {
builtIn.add(value);
}
builtIn.add(0, 0);
System.out.println(builtIn);
}
}capacity 2, copies in total 1
capacity 4, copies in total 3
capacity 8, copies in total 7
capacity 16, copies in total 15
size 10, first 0, last 9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]class DynamicArray {
cells: number[] = new Array<number>(1).fill(0);
size = 0;
copies = 0;
append(value: number): void {
this.insert(this.size, value);
}
get(index: number): number {
if (index < 0 || index >= this.size) {
throw new RangeError(`index ${index}`);
}
return this.cells[index];
}
insert(index: number, value: number): void {
if (index < 0 || index > this.size) {
throw new RangeError(`index ${index}`);
}
if (this.size === this.cells.length) {
this.resize(this.cells.length * 2);
}
for (let i = this.size; i > index; i--) {
this.cells[i] = this.cells[i - 1];
}
this.cells[index] = value;
this.size++;
}
private resize(newCapacity: number): void {
const bigger = new Array<number>(newCapacity).fill(0);
for (let i = 0; i < this.size; i++) {
bigger[i] = this.cells[i];
this.copies++;
}
this.cells = bigger;
console.log(`capacity ${newCapacity}, copies in total ${this.copies}`);
}
}
const numbers = new DynamicArray();
for (let value = 1; value <= 9; value++) {
numbers.append(value);
}
numbers.insert(0, 0);
console.log(`size ${numbers.size}, first ${numbers.get(0)}, last ${numbers.get(numbers.size - 1)}`);
const builtIn: number[] = Array.from({ length: 9 }, (_, i) => i + 1);
builtIn.splice(0, 0, 0);
console.log(`[${builtIn.join(", ")}]`);capacity 2, copies in total 1
capacity 4, copies in total 3
capacity 8, copies in total 7
capacity 16, copies in total 15
size 10, first 0, last 9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]The built-ins work the same way underneath. Python's list, Java's ArrayList and a TypeScript array append in amortised O(1) and shift on an insert at an index, as insert(0, 0), add(0, 0) and splice(0, 0, 0) do in the last lines. They differ in the growth factor: CPython's list grows by about an eighth, Java's ArrayList by half, and the ECMAScript standard, which defines the language TypeScript compiles to, leaves growth to the engine. Use the built-in in real code; writing the class once is how its costs stop being a surprise.
← → move through sections and cards