Array

An array is a contiguous block in RAM. For example [1, 3, 5] (integers), each takes 4 bytes (32 bits), so addresses might be $0, $4, $8. For chars like ['A', 'B', 'C'], its 1 byte each: $0, $1, $2. The key is everything is next to each other, and we access via indexes starting at 0.

Note that integers are often 32-bit: 1 is 31 zeros and a 1 at the end in binary. Arrays are simple, their memory layout matches how I think of them in code.

Types of Arrays

There are basically two types of arrays:

Static Array: In this type of array, memory is allocated at compile time with a fixed size. We cannot alter or update the size of the array once its created, that's the big limitation when compared to dynamic ones.
Dynamic Array: In this type of array, memory is allocated at run time without a fixed size. If a user wants to declare a random size for an array we won't use a static one, instead, a dynamic array comes in handy. It's used to specify (and change) the size during the run time of any program.

Note: Python and JS/TS default to dynamic arrays, unlike C/C++/Java.

Static Arrays

Reading

Reading is fast, O(1) because RAM is random access (can jump to any address instantly). Index maps directly to the memory address.

Looping through is O(n), obviously, since you hit each element.

my_array = [0] * 3
my_array[0] = 1
my_array[1] = 3
my_array[2] = 5
 
# Read index 0
print(my_array[0])  # 1
 
# Loop
for value in my_array:
    print(value)  # 1 3 5

const myArray: number[] = new Array(3).fill(0);
myArray[0] = 1;
myArray[1] = 3;
myArray[2] = 5;
 
console.log(myArray[0]); // 1
 
for (const value of myArray) {
    console.log(value) // 1 3 5
}

Writing

If you want to overwrite an existing spot, just place the new value at the index, O(1).

Adding to the end (if there's space)? Also O(1): Track a count var, write there, increment.

Removing? Overwrite with None/null and decrement count, still O(1).

Insert/Remove in the Middle

This is where it hurts: O(n) worst case (on average) because you have to shift elements to keep contiguity.

Insert: Slide everything right from a spot, then drop in the new value.
Remove: Slide left to fill the gap.

Example: Inserting at the start (worst shift).

my_array = [5, 6, 0]
for i in range(len(my_array) - 1, 0, -1): # Shift right
    my_array[i] = my_array[i - 1];
my_array[0] = 4
print(my_array) # [4, 5, 6]

const myArray: number[] = [5, 6, 0];
for (let i = myArray.length - 1; i > 0; i--) { // Shift right
    myArray[i] = myArray[i - 1];
}
myArray[0] = 4;
console.log(myArray) // [4, 5, 6]

Trade offs

Good for fast access if size known. Bad for frequent inserts/removes in middle or growing in size. In Python/TS, arrays are dynamic by default, so I rarely hit this, but good to know for lower-level stuff.

Implementation

Full code with tests in the git repo.

class StaticArray:
    def __init__(self, capacity):
        self._array = [0] * capacity
        self._length = 0
        self._capacity = capacity
    
    def insert_end(self, n):
        if self._length < self._capacity:
            self._array[self._length] = n
            self._length += 1
            return True
        return False # Full, no insertion
 
    def remove_end(self):
        if self._length > 0:
            self._array[self._length - 1] = 0
            self._length -= 1
            return True
        return False # Empty, no removal
 
    def insert_middle(self, i, n):
        if i < 0 or i > self._length or self._length >= self._capacity:
            return False # Invalid index or full
        # Shift starting from the end to i
        for index in range(self._length - 1, i - 1, -1):
            self._array[index + 1] = self._array[index]
        # Insert at i
        self._array[i] = n
        self._length += 1
        return True
 
    def remove_middle(self, i):
        if i < 0 or i >= self._length:
            return False # Invalid index
        # Shift starting from i + 1 to the end
        for index in range(i + 1, self._length):
            self._array[index - 1] = self._array[index]
        # No need to "remove" self._array[i], since we shifted
        self._array[self._length - 1] = 0 # Optional: clear the last spot
        self._length -= 1
        return True
 
    def print_array(self):
        for i in range(self._capacity):
            print(self._array[i])
    
    def is_full(self):
        return self._length == self._capacity
 
    def is_empty(self):
        return self._length == 0
 
    def get_length(self):
        return self._length
 
    def get_capacity(self):
        return self._capacity

export class StaticArray {
    private _array: number[];
    private _length: number;
    private _capacity: number;
 
    constructor(capacity: number) {
        this._array = new Array(capacity).fill(0);
        this._length = 0;
        this._capacity = capacity;
    }
 
    insertEnd(n: number): boolean {
        if (this._length < this._capacity) {
            this._array[this._length] = n;
            this._length += 1;
            return true;
        }
        return false; // Full, no insertion
    }
 
    removeEnd(): boolean {
        if (this._length > 0) {
            this._array[this._length - 1] = 0;
            this._length -= 1;
            return true;
        }
        return false; // Empty, no removal
    }
 
    insertMiddle(i: number, n: number): boolean {
        if (i < 0 || i > this._length || this._length >= this._capacity) {
            return false; // Invalid index or full
        }
        // Shift starting from the end to i
        for (let index = this._length - 1; index >= i; index--) {
            this._array[index + 1] = this._array[index];
        }
        // Insert at i
        this._array[i] = n;
        this._length += 1;
        return true;
    }
 
    removeMiddle(i: number): boolean {
        if (i < 0 || i >= this._length) {
            return false; // Invalid index
        }
        // Shift starting from i + 1 to the end
        for (let index = i + 1; index < this._length; index++) {
            this._array[index - 1] = this._array[index];
        }
        // No need to "remove" this._array[i], since we shifted
        this._array[this._length - 1] = 0; // Optional: clear the last spot
        this._length -= 1;
        return true;
    }
 
    printArray(): void {
        for (let i = 0; i < this._capacity; i++) {
            console.log(this._array[i]);
        }
    }
 
    isFull(): boolean {
        return this._length === this._capacity;
    }
 
    isEmpty(): boolean {
        return this._length === 0;
    }
 
    getLength(): number {
        return this._length;
    }
 
    getCapacity(): number {
        return this._capacity;
    }
}

Dynamic Arrays

Dynamic arrays fix the main issue with static ones: the fixed size. They can grow (or shrink) as needed, making them way more flexible. In Python and JS this is the default array type. In Java, if you want a dynamic array you use ArrayList, and vector in C++.

When you create a dynamic array, it starts with some initial capacity (often some default like 10, but varies). The "length" tracks how many elements are actually in use, starting at 0. You don't have to specify a size upfront.

How it works

Pushing: Adding to the end is O(1), it places the value in the next spot and updates the length.
Popping: Removing from the end is also O(1), just decrement the length.

If you run out of space when appending, it allocates a new array double the current capacity, copies all elements over (O(n) for that step), then adds the new one. The old array gets deallocated.

Why double? It minimises how often you resize. Resizing is O(n), but it happens infrequently, this gives it amortised O(1) time for appends overall, meaning on average its constant time. (The cost is dominated by the last resize, totalling ~2n operations for n elements, which simplifies down to O(n) total, or O(1) per append).

Reading/writing by index is still O(1), like static. Looping is O(n). Insert/remove in the middle is O(n) worst case, no amortisation here lol.

Trade offs

Great for variable sizes and frequent appends/pops. The resizing overhead is rare, so it's efficient. Downside: occasional O(n) spikes on resize and still bad for middle inserts/removes. Use when you need flexibility without knowing size in advance.

Examples

my_list = []  # Starts empty, dynamic
my_list.append(1)  # Push
my_list.append(3)
my_list.append(5)
print(my_list[0])  # 1, O(1) read
print(my_list.pop())  # 5, O(1) pop
for value in my_list:
    print(value)  # 1 3

const myArray: number[] = [];  // Starts empty, dynamic
myArray.push(1);  // Push
myArray.push(3);
myArray.push(5);
console.log(myArray[0]);  // 1, O(1) read
console.log(myArray.pop());  // 5, O(1) pop
for (const value of myArray) {
    console.log(value);  // 1 3
}

Inserting in the middle (e.g. at index 1)

my_list = [1, 3, 5]
my_list.insert(1, 2)  # Shifts right from index 1
print(my_list)  # [1, 2, 3, 5]

const myArray: number[] = [1, 3, 5];
myArray.splice(1, 0, 2);  // Shifts right from index 1
console.log(myArray);  // [1, 2, 3, 5]

Implementation

Full code with tests in the git repo.

class DynamicArray:
    def __init__(self):
        self._array = [0] * 1 # Start small, capacity of 2.
        self._length = 0
        self._capacity = 1
    
    def resize(self):
        # Create new array of double capacity
        self._capacity *= 2
        new_array = [0] * self._capacity
 
        #Copy elements to new_array
        for i in range(self._length):
            new_array[i] = self._array[i]
        self._array = new_array
    
    # Insert n in the last position of the array
    def pushback(self, n):
        if self._length == self._capacity:
            self.resize()
        # Insert at next empty position
        self._array[self._length] = n
        self._length += 1
 
    # Remove the last element in the array
    def popback(self):
        if self._length > 0:
            self._length -= 1
 
    # Get value at i-th index
    def get(self, i):
        if i < self._length:
            return self._array[i]
        raise IndexError("Index out of bounds")
 
    # Insert at the i-th index
    def insert(self, i, n):
        if i < 0 or i > self._length:
            raise IndexError("Index out of bounds")
        if self._length == self._capacity:
            self.resize()
        # Shift right from i to end
        for j in range(self._length, i, -1):
            self._array[j] = self._array[j - 1]
        self._array[i] = n
        self._length += 1
        
    def print(self):
        for i in range(self._length):
            print(self._array[i])
        print()

export class DynamicArray {
    private _array: number[];
    private _length: number = 0;
    private _capacity: number = 1;
 
    constructor() {
        this._array = new Array(1).fill(0); // Start small explicit zeros
    }
 
    private resize(): void {
        this._capacity *= 2;
        const new_array: number[] = new Array(this._capacity).fill(0);
        for (let i = 0; i < this._length; i++) {
            new_array[i] = this._array[i];
        }
        this._array = new_array;
    }
 
    pushback(n: number): void {
        if (this._length === this._capacity) {
            this.resize();
        }
        this._array[this._length] = n;
        this._length++;
    }
 
    popback(): void {
        if (this._length > 0) {
            this._length--;
        }
    }
 
    get(i: number): number {
        if (i < 0 || i >= this._length) {
            throw new RangeError("Index out of bounds");
        }
        return this._array[i];
    }
 
    insert(i: number, n: number): void {
        if (i < 0 || i > this._length) {
            throw new RangeError("Index out of bounds");
        }
        if (this._length === this._capacity) {
            this.resize();
        }
        for (let j = this._length; j > i; j--) {
            this._array[j] = this._array[j - 1];
        }
        this._array[i] = n;
        this._length++;
    }
 
    print(): void {
        const output = this._array.slice(0, this._length).join(" ");
        console.log(output || "");
    }
 
    getLength(): number {
        return this._length;
    }
 
    getCapacity(): number {
        return this._capacity;
    }
}