Data Structures & Algorithms
Arrays and Strings
An array is a collection of values stored in a fixed, indexed order, so any element can be reached directly by its position. A string is, conceptually, an array of characters, with its own conventions in most languages, commonly immutability, meaning a string cannot be changed in place once created. Python's built-in list is not a fixed-size array in the low-level sense; it is a dynamic array that manages its own resizing, which explains both its convenience and a few of its real performance quirks.
Why it matters
- Nearly every other data structure is built on an array underneath
- A hash table's buckets, a stack or queue's backing storage, and a dynamic array itself are all, at some level, an array plus extra logic.
- Index-based access is the baseline every other lookup gets compared against
- O(1) access by position is the fastest possible lookup any structure offers, which is exactly why other structures are described in terms of how close they get to it.
- String processing is one of the most common everyday programming tasks
- Parsing input, validating a format, and building output text all reduce to operations on sequences of characters.
- Bounds and off-by-one mistakes on arrays are extremely common
- Reading or writing past the end of an array is undefined behavior in some languages, and has historically been the root cause of a large share of real security vulnerabilities.
Indexing and contiguous storage
Elements of an array sit in order, each reachable by a numeric index, starting at 0 in Python and most other mainstream languages. Because the elements are laid out contiguously in memory, the address of any element can be computed directly from its index - this is what makes indexed access O(1), regardless of how large the array is or where in it the index points. Python also supports negative indexing, where -1 refers to the last element, and slicing, which produces a new list or string covering a range of positions.
numbers = [10, 20, 30, 40, 50]
print(numbers[0]) # 10
print(numbers[-1]) # 50, the last element
print(numbers[1:4]) # [20, 30, 40], a new listArrays that grow: Python's list vs a fixed-size array
A genuinely fixed-size array, as used in lower-level languages, is allocated once at a set length and cannot grow. Python's list is a dynamic array: it manages a backing buffer that is usually larger than the current number of elements, so append is usually O(1) - it just writes into the next free slot. Occasionally the buffer fills up and the list has to allocate a new, larger buffer and copy every existing element into it, which is an O(n) operation; averaged out over many appends, this happens rarely enough that append is still described as amortized O(1).
Strings as immutable sequences of characters
A Python string behaves like a sequence - it can be indexed, sliced, and looped over - but it cannot be changed in place. Every operation that looks like it modifies a string actually builds and returns a new string, leaving the original untouched. This matters for performance: building a large string by repeatedly concatenating inside a loop creates a new string on every single iteration, copying everything built so far each time, which adds up to quadratic total cost. Collecting the pieces in a list and joining them once at the end avoids the repeated copying entirely.
# quadratic: every += copies everything accumulated so far
result = ''
for word in ['a', 'b', 'c']:
result += word
# linear: pieces are joined once, at the end
result = ''.join(['a', 'b', 'c'])Mistakes people make here
- Off-by-one indexing errors, especially with slice endpoints
- Python slices are inclusive of the start and exclusive of the stop, so a slice from 1 to 4 gives three elements, not four - a convention that is consistent once learned but catches almost everyone at least once.
- Concatenating strings in a loop instead of collecting and joining
- Each concatenation on a string creates an entirely new string and copies everything accumulated so far into it, turning what looks like a simple loop into quadratic total work as the string grows.
- Assuming insertion or deletion anywhere in an array is O(1)
- Only insertion or deletion at the end of a Python list is close to O(1); inserting or deleting anywhere else requires shifting every later element over by one position, which is O(n).
- Mutating a list while iterating over it
- Removing or inserting elements from a list during a for loop over that same list shifts the positions of the remaining elements out from under the loop's index, silently skipping or repeating items with no error raised.
Strengths and trade-offs
Where it is strong
- O(1) random access by index - the fastest lookup by position any structure offers.
- Contiguous memory layout is cache-friendly, so sequential scans over an array tend to be fast in practice, not just on paper.
- A simple mental model - numbered slots - which is why nearly every other structure is built from one underneath.
The trade-offs
- Inserting or deleting anywhere but the end costs O(n), because every later element has to shift over to make or close the gap.
- A genuinely fixed-size array wastes space if allocated for a worst case that rarely happens, or fails outright if the estimate is too low.
- Dynamic arrays like Python's list hide the occasional O(n) resizing cost behind what otherwise looks like a simple append, which can surprise you in a performance-sensitive tight loop.
Who needs this
Everyone - the array, in the form of Python's list, is usually the very first real data structure anyone uses, often before the term data structure has even come up.
Questions about arrays and strings
- Is a Python list the same thing as an array?
- Close, but not identical. It behaves like a dynamic array, indexed, ordered, contiguous in the sense that matters for access speed, but unlike a low-level fixed array, it resizes itself automatically and can hold values of different types at once, since it actually stores references to objects rather than the raw values themselves.
- Why is indexing O(1) but searching for a value O(n)?
- Indexing computes the exact memory location directly from the index, with no searching involved. Searching for a value means checking elements one at a time, in the worst case all of them, until a match is found or the array is exhausted - there is no shortcut without additional structure, like keeping the array sorted or building a hash table.
- Why is repeated string concatenation inside a loop slow?
- Because strings are immutable - each concatenation does not modify the existing string, it builds an entirely new one containing everything before it plus the addition, copying all of the previous content again in the process. Over many iterations that repeated copying adds up to quadratic total work.
- What's the actual difference between a string and an array of characters?
- Conceptually very little - a string is an ordered sequence of characters and supports the same indexing and slicing an array does. The practical difference in most languages, Python included, is that strings are immutable and carry text-specific methods that a generic array of arbitrary values would not have.