Array Fundamentals & Traversal

Jr Codex DSA Notes

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

Table of Contents

1. Python Lists as Arrays
2. Indexing & Slicing Recap
3. Traversal Patterns
4. In-Place vs. New-Array Operations
5. Complexity of Common List Operations
6. Summary & Next Steps

1. Python Lists as Arrays

In many languages, an "array" is a fixed-size, contiguous block of memory holding elements of one type. Python's list is more flexible (resizable, mixed types) but internally behaves like a dynamic array — a contiguous block that Python grows automatically. For DSA purposes, treat a Python list as the array: this module analyzes it the way a DSA course would analyze a C-style array, with Python's conveniences layered on top.

scores = [88, 95, 72, 60, 99]

2. Indexing & Slicing Recap

You met this in Python Notes Module 1 — worth a quick refresher since every array algorithm leans on it:

scores = [88, 95, 72, 60, 99]
 
scores[0]        # 88   — first element
scores[-1]       # 99   — last element
scores[1:3]      # [95, 72]  — slice, end-exclusive
scores[::-1]     # [99, 60, 72, 95, 88]  — reversed copy

3. Traversal Patterns

"Traversal" just means visiting every element — but how you traverse shapes both readability and complexity:

scores = [88, 95, 72, 60, 99]
 
# Value-based traversal — use when you don't need the position
for score in scores:
    print(score)
 
# Index-based traversal — use when you need the position too
for i in range(len(scores)):
    print(i, scores[i])
 
# Both at once
for i, score in enumerate(scores):
    print(i, score)

All three are O(n) — one pass over the data. The choice is about what information you need, not performance.

4. In-Place vs. New-Array Operations

This distinction determines your space complexity (Module 1, Chapter 4) and matters constantly in DSA problems, which often specifically ask for an "in-place" solution:

scores = [88, 95, 72, 60, 99]
 
# In-place: modifies the existing list, O(1) auxiliary space
scores.reverse()
 
# New array: builds a separate list, O(n) auxiliary space
reversed_scores = scores[::-1]

A function that mutates its input list and returns None is a strong signal it's operating in place; a function that returns a new list is not. Interview problems phrased as "modify the array in place" or "without using extra space" are asking you to use the first style.

5. Complexity of Common List Operations

This table is worth memorizing — most array-based algorithm analysis in later chapters depends on it:

The key insight: operations at the end of a list are cheap (O(1)); operations at the start or middle are expensive (O(n)) because of the shifting required. This single fact motivates why later modules introduce structures like linked lists (Module 6) and deques (Module 5) for workloads that need fast insertion/deletion at both ends.

6. Summary & Next Steps

Key Takeaways

• Python's list behaves like a dynamic array — contiguous storage with automatic resizing.
• In-place operations (O(1) space) mutate the existing list; new-array operations (O(n) space) return a separate list — interview problems often specify which they want.
• Index access and end-of-list operations are O(1); start/middle insertion, deletion, and search are O(n) — because of shifting or scanning.
• This complexity table underlies almost every array algorithm in the rest of this module.

Concept Check

1. Why is scores.append(x) considered O(1) amortized rather than strictly O(1)?
2. Why does scores.insert(0, x) cost O(n) even though it inserts just one element?
3. What signal in a function's design suggests it's operating in place vs. building a new array?

Next Chapter

→ Chapter 2: Searching, Insertion & Deletion

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