Static Array
Array is a contiguous block of data (memory is allocated to a process or file needing it).
What is static array?
Static Array = Fixed size array + type
Once you declared, the size of the array and type cannot be changed. If the array is full, then you cannot add additional elements into it.
ℹ️
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 |
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.
class StaticArray:
def __init__(self, *, array: list = [], capacity: int) -> None:
self.array = array if array else [0] * capacity
self.capacity = capacity
def append(self, value) -> None:
if len(self.array) < self.capacity:
self.array[len(self.array)] = value
def insert(self, value, index: int) -> None:
# range(start, stop, step)
# loop from backward, 3, 2, 1
# [1, 2, 3] = [1, 4, 2, 3]
# index = 1
# loop: 2 1, 0 won't go as it stop at 0
for i in range(len(self.array) - 1, index - 1, -1):
self.array[i + 1] = self.array[i]
self.array[index] = value
def remove(self, index: int) -> None:
if index == len(self.array) - 1:
self.array[len(self.array) -1] = 0
else:
for i in range(index, len(self.array) - 1):
self.array[i] = self.array[i + 1]
self.array[i + 1] = 0
def traverse(self) -> None:
for i in range(len(self.array)):
print(self.array[i])