Static Array

What is static array?

Static array is an array with a fixed size. The size of the array must be declared at the time of creation. The size of the array cannot be changed after it is created.

If the array is full, you cannot add additional elements into it.

The memory is typically allocated at compile time. This means that the size of the array must be known at compile time and cannot be changed at runtime. The elements of the array are stored in contiguous block of memory, which allows for efficient access to the elements using their index.

Runs in constant time O(1), single-operation. This means that regardless of the size of the array, the time taken to access the element will be unaffected.

Operation	Big-O Time	Notes
Access	O(1)	-
Insert/Remove End	O(1)	-
Insert/Remove Middle	O(n)	You have to shift the values

Advantages and Disadvantages

Advantages

Simple to implement
Efficient for accessing elements

Disadvantages

Fixed size - which can lead to wasted memory if the array is not fully utilized or insufficient memory if the array is too small.
Insertion and deletion can be costly as elements may need to be shifted.

Initialize Static Array

A static array can be initialized in two ways:

with initial values
without initial values, normally the languages will by default set the array elements to 0.

Static Array Implementation

Reading from Static Array

Info

O(1) - If the number of operations does not grow as the input size grows, then we say that the algorithm runs in constant time, or O(1) time.

To read from a static array, you can use the index of the element you want to access. The index starts from 0. Now, accessing the element in a static array is done in constant time O(1), because each index maps directly to a specific memory location.


static_array = [1, 2, 3, 4, 5]
 
print(static_array[0])  # Output: 1
print(static_array[2])  # Output: 3

Traverse Static Array

Info

O(n) - If the number of operations grows linearly with the input size, then we say that the algorithm runs in linear time, or O(n) time.

To traverse a static array, you can use a loop to iterate through each element in the array. So, the time complexity for traversing a static array is O(n), where n is the number of elements in the array. This is because you need to visit each element in the array once.


for i in range(len(static_array)):
    print(static_array[i])
 
# OR
 
for value in static_array:
    print(value)
 
# OR
 
i = 0
while i < len(static_array):
    print(static_array[i])
    i += 1

Delete from Static Array

For deleting an element from a static array, there are two scenarios:

Deleting the last element - this can be done in constant time O(1), as you can simply reduce the count of elements in the array.
Deleting an element at a specific index - this requires shifting all subsequent elements to the left, resulting in a time complexity of O(n).


# count = len(static_array)
def remove(index: int) -> None:
    if not 0 <= index <Tabs count:
        raise IndexError("Index out of bounds.")
    
    # Shift all elements from the next index to the left
    for i in range(index, count - 1):
        static_array[i] = static_array[i + 1]
 
    # Clear the last element and update the count
    static_array[count - 1] = 0  # or None, depending on your use case
    count -=1

Insert into Static Array

Inserting an element into a static array also has two scenarios:

Inserting at the end of the array - this can be done in constant time O(1), as long as there is enough capacity in the array.
Inserting at a specific index - this requires shifting all subsequent elements to the right, resulting in a time complexity of O(n).


# count = len(static_array) --- track the current number of elements
# capacity = len(static_array)
def insert(index: int, value: int) -> None:
    if count == capacity:
        raise OverflowError("Array is at full capacity.")
 
    # Check if index is within the valid range for insertion
    if not 0 <= index <= count:
        raise IndexError("Index out of bounds.")
    
    # Shift all elements from the target index to the right
    # range(start, stop, step)
    # - start: The first number in the sequence
    # - stop: The sequence will stop before this number
    # - step: The difference between each number in the sequence
 
    # For example, if we want to insert 4 at index 1 in the array [1, 2, 3]:
    # [1, 2, 3] = [1, 4, 2, 3]
    # count = 3, index = 1, step = -1
    # loop: 3, 2, (1 won't go as it stop at 1)
    # i = 3 -> static_array[3] = static_array[2] [1, 2, 3, 3]
    # i = 2 -> static_array[2] = static_array[1] [1, 2, 2, 3]
 
    for i in range(count, index, -1):
        static_array[i] = static_array[i - 1]
 
    # Insert the new value and update the count
    static_array[index] = value
    count += 1

Static Array Class Implementation

python

static_array.py


class StaticArray:
    def __init__(self, capacity: int) -> None:
        if not isinstance(capacity, int) or capacity <= 0:
            raise ValueError("Capacity must be a positive integer.")
        self._items = [None] * capacity
        self._capacity = capacity
        self._count = 0 # Track the current number of elements
    
    def __len__(self) -> int:
        return self._count
 
    # this method is called when you do array[index]
    def __getitem__(self, index: int) -> int:
        if not 0 <= index < self._count:
            raise IndexError("Index out of bounds.")
        return self._items[index]
 
    def __setitem__(self, index: int, value: int) -> None:
        if not 0 <= index < self._count:
            raise IndexError("Index out of bounds.")
        self._items[index] = value
 
    def append(self, value: int) -> None:
        if self._count == self._capacity:
            raise OverflowError("Array is at full capacity.")
        self._items[self._count] = value
        self._count += 1
 
    def insert(self, index: int, value: int) -> None:
        if self._count == self._capacity:
            raise OverflowError("Array is at full capacity.")
 
        if not 0 <= index <= self._count:
            raise IndexError("Index out of bounds.")
 
        for i in range(self._count, index, -1):
            self._items[i] = self._items[i - 1]
 
        self._items[index] = value
        self._count += 1
 
    def remove(self, index: int) -> int:
        if not 0 <= index < self._count:
            raise IndexError("Index out of bounds.")
        
        # Store the value to be returned
        value = self._items[index]
 
        # Shift all elements from the next index to the left
        for i in range(index, self._count - 1):
            self._items[i] = self._items[i + 1]
        self._items[self._count - 1] = None
        self._count -= 1
        return value
 
    def traverse(self) -> None:
        for i in range(self._count):
            print(self._items[i])
 
# Example usage
my_array = StaticArray(5)
my_array.append(1)
my_array.append(2)
my_array.append(3)
my_array.traverse()  # Output: 1 2 3
 
my_array.insert(1, 4)
my_array.traverse()  # Output: 1 4 2 3
 
removed_item = my_array.remove(2)
print(f"Removed item: {removed_item}") # Output: Removed item: 2
my_array.traverse()  # Output: 1 4 3
 
print(my_array[0])  # Output: 1
my_array[0] = 10
print(my_array[0])  # Output: 10

Static Array Visualization

Array Visualization (32-bit Integers)

0x1000

[0]

0x1004

[1]

0x1008

[2]

0x100C

[3]

0x1010

[4]

0x1014

[5]

0x1018

[6]

0x101C

[7]

Array Length: 8/8 | Each cell: 4 bytes (32-bit integer) |

Read

Traverse

Insert

Delete

Animation Controls

Animation Speed (ms)

Array Operations

Read from Array

Delete from Array

Insert at Index

Array is at maximum capacity (8)

Insert at End

Array is at maximum capacity (8)