Array Operations: Insert, Delete, and Search Explained

The three operations you perform on an array constantly are insert, delete, and search. Their cost depends entirely on where you act: touching the end is cheap, but touching the front or middle forces neighboring elements to shift. This page shows each operation in code and pins down its time complexity so you can reason about performance before you write a line.

If you haven’t yet, skim arrays introduction and dynamic arrays first.

Inserting at the end (append)

Appending writes into spare capacity, so it’s O(1) amortized for a dynamic array.

#include <vector>
void append(std::vector<int>& a, int value) {
    a.push_back(value);        // O(1) amortized
}

import java.util.ArrayList;
void append(ArrayList<Integer> a, int value) {
    a.add(value);              // O(1) amortized
}

function append(a, value) {
  a.push(value);               // O(1) amortized
}

def append(a, value):
    a.append(value)            # O(1) amortized

Inserting at an index (shift right)

Inserting anywhere else must move every later element one slot to the right to make room — O(n) in the worst case.

// insert value at position idx
void insertAt(std::vector<int>& a, int idx, int value) {
    a.insert(a.begin() + idx, value); // shifts later elements: O(n)
}

// insert value at position idx
void insertAt(ArrayList<Integer> a, int idx, int value) {
    a.add(idx, value);                // shifts later elements: O(n)
}

// insert value at position idx
function insertAt(a, idx, value) {
  a.splice(idx, 0, value);            // shifts later elements: O(n)
}

# insert value at position idx
def insert_at(a, idx, value):
    a.insert(idx, value)              # shifts later elements: O(n)

Deleting at an index (shift left)

Deleting leaves a gap, so every later element shifts one slot left to close it — again O(n).

void deleteAt(std::vector<int>& a, int idx) {
    a.erase(a.begin() + idx);   // shifts later elements left: O(n)
}

void deleteAt(ArrayList<Integer> a, int idx) {
    a.remove(idx);              // shifts later elements left: O(n)
}

function deleteAt(a, idx) {
  a.splice(idx, 1);            // shifts later elements left: O(n)
}

def delete_at(a, idx):
    del a[idx]                 # shifts later elements left: O(n)

Tip: If order does not matter, you can delete in O(1) by overwriting the target with the last element and removing the last slot — the “swap-and-pop” trick. It avoids the shift entirely.

Searching by value

In an unsorted array you have no choice but to check elements one by one — linear search, O(n).

int indexOf(const std::vector<int>& a, int target) {
    for (int i = 0; i < (int)a.size(); i++)
        if (a[i] == target) return i;
    return -1; // not found
}

int indexOf(int[] a, int target) {
    for (int i = 0; i < a.length; i++)
        if (a[i] == target) return i;
    return -1; // not found
}

function indexOf(a, target) {
  for (let i = 0; i < a.length; i++)
    if (a[i] === target) return i;
  return -1; // not found
}

def index_of(a, target):
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1  # not found

If the array is sorted, binary search finds an element in O(log n) by repeatedly halving the range — a huge win on large inputs.

Complexity cheat sheet

Operation	Best	Worst
Access / update by index	O(1)	O(1)
Insert / delete at end	O(1) amortized	O(n) (on resize)
Insert / delete at index	O(n)	O(n)
Search (unsorted)	O(1)	O(n)
Search (sorted, binary)	O(1)	O(log n)

When the costs bite

Arrays shine when you mostly read by index and append. If your workload is insert/delete-heavy in the middle, the repeated O(n) shifting adds up — consider a linked list or, for key-based lookup, a hash table.

Ready to apply these? Head to the array exercises.