Arrays & Strings: The Workhorse Data Structure

The array is the data structure you've been using since your very first program, probably without thinking of it as a "data structure" at all. It's also the one whose costs people guess wrong most often. Confidently grabbing item number five is instant, but checking whether a value is in the list is not. The difference comes straight from how arrays sit in memory.

Contiguous memory is the whole secret

An array stores its elements contiguously, one right after another in a single unbroken block of memory. That single design choice explains every cost an array has, good and bad.

Because the elements are evenly spaced and packed together, the computer can jump to any one of them with arithmetic, not searching. It knows where the block starts, it knows each element's size, so the address of item i is just start + i × size. One multiply, one add, done, regardless of whether i is 2 or 2 million.

That's why prices[500000] is exactly as fast as prices[0]. The machine doesn't walk through the first 500,000 items to reach it. It computes the address directly. This is the array's superpower, and it's O(1), constant time no matter the size.

What's cheap, what's not

The flip side of that packed layout is that some operations are expensive, and it's worth knowing which before you reach for one in a hot loop.

• Index by position, O(1). "Give me item 7." Direct address math, as above. Instant.
• Search by value, O(n). "Is 42 in this list, and where?" The array has no idea where a value lives (only positions are addressable), so it checks elements one by one until it finds a match or runs out. Worst case, it touches every element.
• Insert or delete in the middle, O(n). To open a gap at position 3, every element after it has to shuffle one slot over to keep the block contiguous. Add at the very end and it's usually cheap. Insert in the middle and you pay for the shift.

So "look it up by position" and "find it by value" feel similar but live in different complexity classes. Confusing the two is how an innocent-looking if x in big_list inside a loop turns into accidental O(n²).

Strings are arrays of characters

A string is an array of characters with a couple of extra rules. The big one in Python: strings are immutable. You can read any character by index in O(1) (name[0] is instant) but you can't change a character in place. name[0] = "X" raises an error.

"Editing" a string really means building a new one. name.upper(), slicing, and concatenation each produce a fresh string and leave the original untouched. That's usually fine, but it's why gluing strings together inside a big loop can sneak up on you. Each += may copy the whole thing so far. When that matters, collect the pieces in a list and "".join(...) them once at the end.

Two pointers: scan from both ends

A pattern that shows up constantly with arrays: instead of one index crawling left to right, use two, one starting at each end, walking toward the middle. On a sorted array it's almost magic for "find a pair that sums to a target."

The idea: if the two ends sum to too much, the only way to shrink the sum is to pull the right pointer left (toward smaller values). If they sum to too little, push the left pointer right (toward larger values). Each step rules out a value for good, so you sweep the whole array in one pass at O(n), instead of checking every pair at O(n²).

Step through it below. Watch the two pointers close in, and notice how each move is forced by whether the current sum overshoots or undershoots the target.

The left and right markers never backtrack, so the total work is one walk across the array. That "two pointers converging" move is one of the highest-value patterns in all of array problems, and the whole next lesson leans on it.

Indexing, slicing, and an in-place reverse

Time to touch the real thing. The block below does the basics (index, negative index, slice) then reverses a list in place with two pointers, swapping the ends inward. No second list, no extra memory beyond a temp swap: O(n) time, O(1) extra space.

The reverse touches each element once on its way to the middle, so doubling the list doubles the swaps — textbook O(n). And it mutates the original rather than allocating a copy, which is the in-place, O(1)-space part. (A string can't be reversed this way, since it's immutable, so you'd build a new one with text[::-1].)

Where to go next

Arrays are fast where it counts, with instant access by position, and slow in the places that surprise people: searching by value and inserting in the middle both walk the whole thing. Knowing which is which, and reaching for two pointers on sorted data, covers a huge share of real array work.

Next: Hash Maps & Sets, the structure that fixes the array's weak spot, turning "is this value in here?" from O(n) into O(1) on average. If list slicing or indexing felt shaky, the Python series has the basics down cold.