Array Operations

Knowing how an array is stored in memory is step one. Step two is understanding what you can do with it.

Arrays support six core operations: access (get an element by index), search (find an element by value), insert (add a new element), delete (remove an element), traverse (visit every element), and update (change a value at an index).

Some of these are instant. Others slow down as the array gets bigger. Knowing the difference is what lets you write fast programs.

ACCESS — O(1), always fast

Accessing an element by index uses the address formula from the previous lesson. One calculation, done.

function access(array, index):
    if index < 0 or index >= array.length:
        error "Index out of bounds"
    return array[index]

Trace with array = [10, 20, 30, 40, 50], accessing index 2:

SEARCH — O(n), takes longer as the array gets bigger

To find an element by value (not index), you have to check each element one by one. You don't know where it is.

function linearSearch(array, target):
    for i = 0 to array.length - 1:
        if array[i] == target:
            return i        // found it at index i
    return -1               // not in the array

Trace with array = [10, 20, 30, 40, 50], searching for 30:

In the worst case, the target is at the very end (or not there at all). You check every element — that's n checks for n elements.

INSERT — O(1) at the end, O(n) anywhere else

Adding to the end (if there's room) is simple:

function insertAtEnd(array, value, currentSize):
    if currentSize >= array.capacity:
        error "Array is full"
    array[currentSize] = value
    currentSize = currentSize + 1

Inserting in the middle is expensive. You have to shift everything after the insertion point one slot to the right to make room:

function insertAt(array, index, value, currentSize):
    if currentSize >= array.capacity:
        error "Array is full"
    if index < 0 or index > currentSize:
        error "Invalid index"
​
    // Shift elements right, starting from the end
    for i = currentSize - 1 down to index:
        array[i + 1] = array[i]
​
    array[index] = value
    currentSize = currentSize + 1

Step-by-step trace — inserting 25 at index 2 in [10, 20, 30, 40, 50]:

We shifted 3 elements. Inserting at the very beginning shifts ALL elements — that's the worst case.

Shift every element one slot to the right:

Write 5 at index 0:

DELETE — O(1) at the end, O(n) anywhere else

Removing the last element is trivial:

function deleteAtEnd(array, currentSize):
    if currentSize == 0:
        error "Array is empty"
    currentSize = currentSize - 1
    // The value is still in memory, but we treat it as outside the valid range

Deleting from the middle requires shifting elements left to fill the gap:

function deleteAt(array, index, currentSize):
    if index < 0 or index >= currentSize:
        error "Invalid index"
​
    // Shift elements left, starting from the deletion point
    for i = index to currentSize - 2:
        array[i] = array[i + 1]
​
    currentSize = currentSize - 1

Step-by-step trace — deleting element at index 1 from [10, 20, 30, 40, 50]:

TRAVERSE — O(n), takes longer as the array gets bigger

Visiting every element. Forward or backward:

function traverseForward(array, size):
    for i = 0 to size - 1:
        visit(array[i])
​
function traverseBackward(array, size):
    for i = size - 1 down to 0:
        visit(array[i])

You visit each element once, so it always takes n steps for n elements.

UPDATE — O(1), always fast

Changing a value at a known index:

function update(array, index, newValue):
    if index < 0 or index >= array.length:
        error "Index out of bounds"
    array[index] = newValue

Same as access — you jump directly to the position and overwrite it.

Operation Summary

Example 1: Counting shifts

Array of 1000 elements. Insert at index 0 (the beginning):

• Shift all 1000 elements one slot right
• Write the new value
• Total: 1001 steps

Insert at index 999 (near the end):

• Shift only 1 element
• Write the new value
• Total: 2 steps

Both are technically O(n) — but in practice, inserting near the end is much faster.

Example 2: Search then delete

A common pattern: "find and remove the value 30 from [10, 20, 30, 40, 50]"

// Step 1: Search for 30
index = linearSearch(array, 30)    // checks until it finds 30 at index 2
​
// Step 2: Delete at index 2
deleteAt(array, 2)                 // shifts 40 and 50 left
​
// Result: [10, 20, 40, 50]