KarChunTStatic 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: 3Traverse 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 += 1Delete 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 -=1Insert 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 += 1Static Array Class Implementation
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: 10Static Array Visualization
Array is at maximum capacity (8)
Array is at maximum capacity (8)
Last updated on