Searching, Insertion & Deletion

Jr Codex DSA Notes

Level: Beginner Prerequisites: Chapter 1 Time to complete: ~20 minutes

Linear Search
Insertion at Start, Middle & End
Deletion at Start, Middle & End
When Arrays Are the Wrong Tool
Summary & Next Steps

1. Linear Search

Searching an unsorted array means checking elements one at a time until you find a match (or exhaust the array):

def linear_search(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1
    # O(n) worst case — the target may be last, or absent (Module 1, Chapter 5)

This is the baseline every other search strategy is compared against. Module 3 introduces binary search, which drops this to O(log n) — but only works if the array is sorted first.

2. Insertion at Start, Middle & End

items = [10, 20, 30, 40]
 
items.append(50)          # end:    O(1) amortized — no shifting
items.insert(2, 25)        # middle: O(n) — elements from index 2 onward shift right
items.insert(0, 5)          # start:  O(n) — every existing element shifts right

Inserting at index 0 in [10, 20, 30, 40]:
─────────────────────────────────────────
  Before:  [10, 20, 30, 40]
  Insert 5 at index 0
  After:   [5, 10, 20, 30, 40]   ← all 4 existing elements shifted right by one
─────────────────────────────────────────

The further from the end you insert, the more elements shift — worst case (inserting at index 0) touches every element, giving O(n).

3. Deletion at Start, Middle & End

The same shifting logic applies in reverse:

items = [10, 20, 30, 40, 50]
 
items.pop()             # end:    O(1) — no shifting
del items[2]              # middle: O(n) — elements after index 2 shift left
del items[0]               # start:  O(n) — every remaining element shifts left

items.remove(value) is worth calling out separately: it first performs a linear search (O(n)) to find the value, then shifts (O(n)) — still O(n) overall, but for two combined reasons, not one.

4. When Arrays Are the Wrong Tool

Arrays are the right choice when you mostly read by index (O(1)) or add/remove at the end (O(1) amortized). They become the wrong choice when your workload is dominated by frequent insertion or deletion at the start or middle, since every such operation costs O(n).

# A workload that punishes arrays: frequently removing from the front
queue = [1, 2, 3, 4, 5]
while queue:
    first = queue.pop(0)     # O(n) EVERY time — shifts all remaining elements
    process(first)
# Over n removals, this totals O(n²) — a hidden trap from Module 1, Chapter 6

This exact pattern — needing fast removal from the front — is why queues get their own data structure in Module 5 (built on collections.deque, which is O(1) at both ends), and why linked lists (Module 6) exist at all: they trade away O(1) index access for O(1) insertion/deletion anywhere, once you already hold a reference to the node.

5. Summary & Next Steps

Key Takeaways

Linear search is O(n) on unsorted data — the baseline that sorted-data techniques (binary search, Module 3) improve on.
Insertion and deletion cost O(1) at the end of an array, but O(n) at the start or middle, due to shifting.
.remove(value) combines an O(n) search with an O(n) shift.
A workload dominated by front-insertion/removal is a signal that an array is the wrong structure — this motivates queues (Module 5) and linked lists (Module 6).

Concept Check

Why does deleting the first element of a 1,000-element list touch all 999 remaining elements?
What two separate costs does .remove(value) combine, and why is it still just O(n) overall (not O(n²))?
What symptom in your code (not just "it's slow") should make you suspect you need a different structure than a plain array?

Next Chapter

→ Chapter 3: Two-Pointer Technique

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index