Arrays and strings — the basics

The two most fundamental data structures, and the handful of operations on them worth knowing cold before anything about complexity or patterns will make sense.

Beginner

4 min read

An array: a numbered row of slots in memory

numbers = [10, 20, 30, 40]

An array (Python calls its version a list) is a sequence of values stored in order, each accessible by its position — its index. Indexing starts at 0, not 1: numbers[0] is 10, the first element; numbers[3] is 40, the fourth and last one. This zero-based indexing is a near-universal convention across programming languages, not a Python quirk, and it trips up almost everyone the first time — the last valid index in an array of length n is n - 1, not n.

numbers[0]        # 10 — access by index
numbers[-1]        # 40 — negative indices count from the end
numbers[1:3]        # [20, 30] — a slice: elements from index 1 up to (not including) 3
len(numbers)        # 4 — the number of elements

Why array access by index is instant, but searching isn't

Accessing numbers[2] is O(1) — constant time, regardless of how large the array is — because the computer can calculate exactly where in memory that element lives directly from its index, with no searching involved. Finding whether a specific value exists in an array (30 in numbers) is a different operation entirely: without more information, the only way to be sure is to check every element one by one, which is O(n) — this distinction, "accessing by known position is fast, searching by value is slow," is the seed of most of the patterns covered in later DSA lessons (the hash map pattern exists specifically to make "does this value exist" fast too).

Common array operations, and their real cost

numbers = [10, 20, 30]
numbers.append(40)         # [10, 20, 30, 40] — add to the end, fast
numbers.insert(0, 5)        # [5, 10, 20, 30, 40] — add at the start, slow
numbers.pop()                 # removes and returns 40, from the end, fast
numbers.remove(20)           # removes the first 20 found, by value, slow

Adding or removing at the end of an array is fast (the array's own memory layout supports it directly). Adding or removing at the beginning or middle is slow, because every element after that point has to physically shift over by one position to make or close the gap — this cost is the entire reason a different data structure (the linked list, covered in its own lesson) exists for cases that need frequent insertion at the front.

A string is really just an array of characters

word = "hello"
word[0]        # "h"
word[-1]        # "o"
word[1:4]        # "ell"
len(word)        # 5

Strings support the same indexing and slicing as arrays, for exactly the reason the name suggests — a string genuinely is a sequence of characters, stored in order, and almost everything that's true about arrays (index access is fast, searching for a substring takes real work) is true about strings too. The one major difference: in Python, strings are immutable — word[0] = "H" raises an error, because a string can't be modified in place. Any "change" to a string actually creates a brand-new string:

word = "hello"
word = "H" + word[1:]    # "Hello" — a new string, word now points at it

Two operations worth knowing cold: reversing and checking membership

numbers = [1, 2, 3]
numbers[::-1]              # [3, 2, 1] — reverse, using slice notation
"hello"[::-1]                # "olleh" — same trick works on strings
 
30 in [10, 20, 30]           # True — membership check
"ell" in "hello"              # True — substring check

[::-1] is a slice with a step of -1 — "walk through this sequence backward, taking every element" — the standard, idiomatic way to reverse a list or string in Python without writing a manual loop. in checks whether a value (or substring) exists anywhere in the sequence, returning True/False — simple to use, but worth remembering it's an O(n) scan under the hood, not free.