Static Arrays

To review, an array is a contiguous block of data. Likewise, it is stored in ram as a contiguous block. When we read or write to an array, we are actually accessing the data stored in the RAM.

Let's say we want to read the first element of the array in figure 1. Arrays have indexes and start at zero. So to read the first element of justAnArray, we need to specify index 0.

# Creating our array
justAnArray = [1, 2, 3]

# Reading the first element to output
print(justAnArray[0])

We can read any element of the array by calling on the index. All of these are O(1) time because we can map it to the part of RAM where it is stored. Like the name implies, random access memory enables us to access any part of the memory quickly. We don’t need to traverse the entire RAM to find the one index we want. Doing so would be O(n) time. However, to traverse the entire array, it would be O(n) time. This can be achieved with a for-loop:

# Create our array
myArr = [1, 2, 3]
  
# Traverse array
for element in myArr:
    print(element)

Static arrays are of fixed size. Since the data in RAM is contiguous, we cannot just add another element. In figure 1, we have 3 elements. Say the address where the data is stored are: $0, $4, $8. We cannot just add another element to the array since we did not allocate memory to it. Address $12 may already be in use for another purpose. We can’t store this fourth element in a random place either, like $404. This would mean the data is not contiguous. We want one array after all, not two. Now, in a language like Python or JavaScript, this may not be something we worry. After all, Python’s array is actually a list type. The length of a list is dynamic and can hold a heterogenous collection of objects.

While this cushion is nice, not all languages are strictly typed. In those languages, all array indices may be filled with '0', ‘NULL’, or another default value when we initialize but not set them. Say we want to delete the last element from justAnArray in figure 1. We are not deleting the space being allocated. We are simply returning the value to the default, uninitialized value. When we delete from the end, deletion is also O(1) time.

# Create our array
arr = ["1", 2, "three"]

# Pop the last element into a variable to store it. Note that pop is not for static arrays.
last_element = arr.pop()
 
print("Element removed: ", last_element)
print("New array: ", arr)
# Output:
# Element removed:  three
# New array:  ['1', 2]

############################
# Create our array
arr = ["1", 2, "three"]

# Another method to remove the last element is to decrease length
def removeLast(arr):
    # Check to make sure there is an element we can remove
    if len(arr) > 0:
        # Decrease length and set last element to null
        arr[length - 1] = -1

print(removeLast(arr))
# Output: ['1', 2, -1]

We can also do list= list[:-1] but this is O(n) time.

Removing at the ith index is different however. We need to shift the elements past index i one spot to the left.

# Create our array
array = ["1", 2, "three"]


# Remove at index
def removeAtIndex(arr, i):
    # Shift at i + 1
    for index in range(i + 1, len(arr)):
        arr[index - 1] = arr[index]
    arr.pop()  # Remove last element once we shifted as it is duplicated.
    return arr


print(removeAtIndex(array, 1))
# Expected: ['1', 'three']
# Result: ['1', 'three']

This is O(n) time because we are shifting many elements after the ith position.

Remove Duplicates from Sorted Array

Intro to BERT

Rongtian Yue