BrunoB.me
Notes

Static Arrays

Data Structures • 5 min read • Level: Beginner

In statically typed languages like Java, C++ and C#, arrays must have a size and type assigned when initialized. These are known as static arrays.

They’re called static because the size of the array cannot change once declared. And once the array is full, it can’t store additional elements. Some dynamically typed languages like Python and JavaScript don’t have static arrays to begin with. They have an alternative, which we’ll discuss in the next lesson.

Let’s cover the key array operations and their associated time complexity.

Reading from an array

To read an individual element from an array we can choose the position we want to access via an index. Below we’ve initialized an array of size 3 called myArray. We also attempt to access an arbitrary element using the index i.

// initialize myArray
int myArray[3] = {1, 3, 5};

// access an arbitrary element, where i is the index of the desired value
myArray[i];
// initialize myArray
int[] myArray = {1, 3, 5};

// access an arbitrary element, where i is the index of the desired value
myArray[i];
// initialize myArray
val myArray = intArrayOf(1, 3, 5)

// access an arbitrary element, where i is the index of the desired value
myArray[i]
# initialize my_array
my_array = [1, 3, 5]

# access an arbitrary element, where i is the index of the desired value
my_array[i]
Array access example
Visualizing element access in an array

Accessing a single element in an array is always instantaneous because each myArray index is mapped to an address in RAM. Regardless of the input array size, the time taken to access a single element is the same. We refer to this operation as O(1) in terms of time complexity.

A common confusion is that O(1) is always fast. This isn’t necessarily true. There could be 1000 operations and the time complexity could still be O(1). If the number of operations doesn’t grow as the size of the input grows, then it’s O(1).

Traversing through an array

We can also read all values in an array by traversing it. Below are examples of how we could iterate through myArray from start to finish using loops.

for (int i = 0; i < length; i++) {
    printf("%d ", myArray[i]);
}

// OR

int i = 0;
while (i < length) {
    printf("%d ", myArray[i]);
    i++;
}
for (int i = 0; i < length; i++) {
    System.out.println(myArray[i]);
}

// OR

int i = 0;
while (i < length) {
    System.out.println(myArray[i]);
    i++;
}
for (i in 0 until length) {
    println(myArray[i])
}

// OR

var i = 0
while (i < length) {
    println(myArray[i])
    i++
}
for i in range(length):
    print(my_array[i])

# OR

i = 0
while i < length:
    print(my_array[i])
    i += 1

The last element in an array is always at index n-1 where n is the size of the array. If our array size is 3, the last accessible index is 2.

To traverse an array of size n, the time complexity is O(n). This means the number of operations grows linearly with the size of the array.

For example, with an array of size 10 we’d perform 10 operations to traverse it; with an array of size 100, we’d perform 100 operations, and so on.

Deleting from an array

Deleting from the end of the array

In statically typed languages, all array indices are filled with 0s or some default value upon initialization, denoting an empty array.

When we want to remove an element at the last index of an array, setting its value to 0/null or -1 is the best we can do. This is known as a soft delete. The element isn’t being “deleted” per se, but overwritten with a value that denotes an empty slot. We’d also reduce the length by 1 since we have one fewer element after deletion.

// Remove from the last position in the array if the array
// is not empty (i.e. length is non-zero).
void removeEnd(int arr[], int length) {
    if (length > 0) {
        // Overwrite last element with some default value.
        // We would also consider the length to be decreased by 1.
        arr[length - 1] = 0;
    }
}
// Remove from the last position in the array if the array
// is not empty (i.e. length is non-zero).
public void removeEnd(int[] arr, int length) {
    if (length > 0) {
        // Overwrite last element with some default value.
        // We would also consider the length to be decreased by 1.
        arr[length - 1] = 0;
    }
}
// Remove from the last position in the array if the array
// is not empty (i.e. length is non-zero).
fun removeEnd(arr: IntArray, length: Int) {
    if (length > 0) {
        // Overwrite last element with some default value.
        // We would also consider the length to be decreased by 1.
        arr[length - 1] = 0
    }
}
# Remove from the last position in the array if the array
# is not empty (i.e. length is non-zero).
def remove_end(arr, length):
    if length > 0:
        # In Python, we can use pop() or set to None
        # We would also consider the length to be decreased by 1.
        arr[length - 1] = None
Deletion at the end of the array
6 is removed/overwritten by 0 or -1 to denote it no longer exists. The length also decreases by 1.

Deleting at an ith index

If instead of deleting at the end we wanted to delete an element at an arbitrary index i, would we be able to do this in O(1)?

We could naively replace it with a 0, but that would break the contiguous nature of our array. Note that deleting from the end of an array doesn’t make it non-contiguous, but deleting from the middle does.

A better approach would be the following:

  1. We’re given the deletion index i.
  2. Iterate starting from i + 1 to the end of the array.
  3. Shift each element one position to the left.
  4. (Optional) Replace the last element with 0 or null to mark it as empty, and decrement the length by 1.
// Remove value at index i before shifting elements to the left.
// Assuming i is a valid index.
void removeMiddle(int arr[], int i, int length) {
    // Shift starting from i + 1 to end.
    for (int index = i + 1; index < length; index++) {
        arr[index - 1] = arr[index];
    }
    // No need to 'remove' arr[i], since we already shifted
}
// Remove value at index i before shifting elements to the left.
// Assuming i is a valid index.
public void removeMiddle(int[] arr, int i, int length) {
    // Shift starting from i + 1 to end.
    for (int index = i + 1; index < length; index++) {
        arr[index - 1] = arr[index];
    }
    // No need to 'remove' arr[i], since we already shifted
}
// Remove value at index i before shifting elements to the left.
// Assuming i is a valid index.
fun removeMiddle(arr: IntArray, i: Int, length: Int) {
    // Shift starting from i + 1 to end.
    for (index in i + 1 until length) {
        arr[index - 1] = arr[index]
    }
    // No need to 'remove' arr[i], since we already shifted
}
# Remove value at index i before shifting elements to the left.
# Assuming i is a valid index.
def remove_middle(arr, i, length):
    # Shift starting from i + 1 to end.
    for index in range(i + 1, length):
        arr[index - 1] = arr[index]
    # No need to 'remove' arr[i], since we already shifted
Deletion at a specific index
Deleting at index 0 requires shifting all elements

The worst case would be needing to shift all elements to the left. This would occur if the target index is the first index of the array. Therefore, the above code is O(n).

Insertion

Inserting at the end

If we want to insert an element at the end of the array, we can simply insert it at the next open position which will be at index length where length is the number of elements in the array.

// Insert n into arr at the next open position.
// Length is the number of 'real' values in arr, and capacity
// is the size (aka memory allocated for the fixed size array).
void insertEnd(int arr[], int n, int length, int capacity) {
    if (length < capacity) {
        arr[length] = n;
    }
}
// Insert n into arr at the next open position.
// Length is the number of 'real' values in arr, and capacity
// is the size (aka memory allocated for the fixed size array).
public void insertEnd(int[] arr, int n, int length, int capacity) {
    if (length < capacity) {
        arr[length] = n;
    }
}
// Insert n into arr at the next open position.
// Length is the number of 'real' values in arr, and capacity
// is the size (aka memory allocated for the fixed size array).
fun insertEnd(arr: IntArray, n: Int, length: Int, capacity: Int) {
    if (length < capacity) {
        arr[length] = n
    }
}
# Insert n into arr at the next open position.
# Length is the number of 'real' values in arr, and capacity
# is the size (aka memory allocated for the fixed size array).
def insert_end(arr, n, length, capacity):
    if length < capacity:
        arr[length] = n

Since we’re writing a single value to the array, the time complexity is O(1).

Note: length is the number of elements inside the array, while capacity refers to the maximum number of elements the array can hold.

Inserting at the ith index

Inserting at an arbitrary index i is more complex since we might be inserting in the middle of the array.

Consider the array [4, 5, 6]. If we need to insert at index i = 1, or i = 0, we can’t overwrite the original value because we’d lose it. Instead, we need to shift all values, starting at index i, one position to the right.

// Insert n into index i after shifting elements to the right.
// Assuming i is a valid index and arr is not full.
void insertMiddle(int arr[], int i, int n, int length) {
    // Shift starting from the end to i.
    for (int index = length - 1; index >= i; index--) {
        arr[index + 1] = arr[index];
    }
    // Insert at i
    arr[i] = n;
}
// Insert n into index i after shifting elements to the right.
// Assuming i is a valid index and arr is not full.
public void insertMiddle(int[] arr, int i, int n, int length) {
    // Shift starting from the end to i.
    for (int index = length - 1; index >= i; index--) {
        arr[index + 1] = arr[index];
    }
    // Insert at i
    arr[i] = n;
}
// Insert n into index i after shifting elements to the right.
// Assuming i is a valid index and arr is not full.
fun insertMiddle(arr: IntArray, i: Int, n: Int, length: Int) {
    // Shift starting from the end to i.
    for (index in length - 1 downTo i) {
        arr[index + 1] = arr[index]
    }
    // Insert at i
    arr[i] = n
}
# Insert n into index i after shifting elements to the right.
# Assuming i is a valid index and arr is not full.
def insert_middle(arr, i, n, length):
    # Shift starting from the end to i.
    for index in range(length - 1, i - 1, -1):
        arr[index + 1] = arr[index]
    # Insert at i
    arr[i] = n
Insertion at a specific index
Inserting 8 at index 1 in the array [4, 5, 6]. Shifting happens before insertion to ensure values aren’t overwritten.

Time Complexity

Operation Big-O Time Notes
Reading O(1) -
Insertion O(n)* If inserting at the end of the array, O(1)
Deletion O(n)* If deleting from the end of the array, O(1)

Conclusion

Static arrays are a fundamental data structure with well-defined operations and predictable complexities:

  • Access: O(1) — Instant via indexing
  • Insert/Delete at end: O(1) — Efficient
  • Insert/Delete in the middle: O(n) — Requires shifting elements

Mastering these operations is essential for more advanced algorithms and dynamic data structures. Understanding when and how to use each operation will help you write more efficient code and solve problems optimally.

Back to Notes Dynamic Arrays