Arrays & Strings

Arrays and strings are the most common ways to store a sequence of related values — a fixed-size or growable list of items for arrays, and a sequence of characters representing text for strings. Both are used constantly and both hide meaningful internal complexity.

An array is an ordered collection of values, usually of the same type, stored so each element can be accessed by its position (index), typically starting at 0. A string is a sequence of characters representing text — in many languages, effectively a specialized array of characters with extra built-in behavior.

Arrays let you work with many related values (a list of scores, a set of sensor readings) as a single collection instead of needing a separate variable name for every individual value. Strings give text its own natural representation and built-in operations (searching, splitting, formatting) rather than forcing every program to manipulate raw characters manually.

A list of a shopping cart's items, a leaderboard's scores, a sentence typed into a search box, a sensor's history of temperature readings over the last hour — arrays and strings appear in essentially every program that deals with more than a single isolated value.

An array is like a row of numbered mailboxes on a street — each mailbox (element) has a specific position (index), and you can walk directly to mailbox #3 without checking every mailbox before it. A string is like a very specific kind of array where every mailbox holds exactly one letter of the alphabet, together spelling out a message when read in order.

Indexing starts at 0 in Python (and most mainstream languages): scores[0] is the first element, not the 'zeroth.' Strings support the same [] indexing syntax as arrays because they behave like a sequence of characters.

Fixed-size arrays (common in C and similar low-level languages) have a size determined at creation and can't grow or shrink afterward; dynamic arrays/lists (Python's list, JavaScript's Array, Java's ArrayList) can grow and shrink at runtime, typically by reallocating a larger underlying block of memory behind the scenes when they run out of room.

Multi-dimensional arrays (a 2D grid, a 3D volume) are typically implemented either as an 'array of arrays' (each row is its own separately allocated array) or as one single flat array with manual index math to simulate multiple dimensions — the two have different memory-layout and performance characteristics.

Strings are immutable in many languages (Python, Java, JavaScript) — an operation that appears to 'modify' a string, like concatenation, actually creates a brand-new string object rather than changing the original in place, which has real performance implications for code that builds up large strings piece by piece in a loop.

Common array/string operations — searching for an element, slicing out a sub-range, sorting, joining/splitting on a delimiter — are worth knowing both conceptually and via your specific language's standard library, since reimplementing them manually is rarely necessary and often less reliable.

Accessing an array index that's out of bounds (negative, or greater than or equal to the array's length), which crashes with an error in many languages, or reads garbage/undefined memory in unsafe languages like C.

Repeatedly concatenating strings in a loop in a language where strings are immutable, unknowingly creating a large number of intermediate string objects and causing quadratic time complexity rather than linear.

Assuming an array's length stays fixed after passing it to a function, when the language allows the function to mutate it (add or remove elements) via a shared reference.

Confusing a string's length in 'characters' as perceived by a human with its length in underlying storage units, especially for text containing multi-byte Unicode characters.

Using a language's built-in string-builder or join mechanism (like Python's ''.join(pieces) or Java's StringBuilder) instead of repeated concatenation, specifically to avoid quadratic-time string building in a loop.

Choosing a dynamic array/list by default for general-purpose collections, and reaching for a fixed-size array specifically when the size is genuinely known and fixed, or when working close to hardware in a systems/embedded context.

Validating array indices (or using a language's built-in bounds-checked access) before indexing into user-supplied or externally derived positions, to avoid out-of-bounds crashes or, in unsafe languages, memory-safety bugs.

Array memory layout and cache behavior A traditional array stores its elements contiguously in memory, one right after another — this contiguity is exactly why indexed access is a constant-time operation (the address of element i is simply the array's base address plus i times the element size) and why iterating sequentially through an array tends to be very cache-friendly, since the CPU can load nearby elements together, a topic explored further in the future Computer Architecture module.

Dynamic array growth strategy When a dynamic array (Python's list, C++'s std::vector, Java's ArrayList) runs out of allocated capacity, it typically allocates a new, larger underlying buffer (often growing by a multiplicative factor like 1.5x or 2x rather than by a fixed small amount), copies existing elements into it, and frees the old buffer. This amortized growth strategy is why appending an element is described as 'amortized constant time' — most appends are cheap, but occasional appends trigger an expensive reallocation and copy.

String interning and encoding Some language runtimes 'intern' certain strings (reusing a single shared copy of identical string literals rather than allocating a new one each time) as a memory and comparison-speed optimization. Separately, the choice of character encoding (UTF-8, UTF-16, UTF-32) affects how many bytes each character occupies and how efficiently operations like length-checking and indexing into arbitrary positions can be performed — some encodings make 'character at position N' a constant-time operation, others make it effectively linear-time due to variable-width characters.

Why is accessing an array element by index a constant-time operation?

Because array elements are stored contiguously in memory, so the address of any element can be computed directly from the array's base address, the element's index, and the fixed size of each element — no searching or traversal is required.

Why can repeated string concatenation in a loop be a performance problem?

In languages where strings are immutable, each concatenation creates an entirely new string object by copying both operands' contents, rather than modifying the original in place. Doing this repeatedly in a loop leads to quadratic time complexity overall, rather than the linear complexity a mutable string-builder approach would achieve.

What does 'amortized constant time' mean for appending to a dynamic array?

Most append operations are cheap (constant time), but occasionally the array must grow its underlying storage, which involves allocating a larger buffer and copying all existing elements — an expensive operation. Averaged ('amortized') over many appends, the typical per-append cost still works out to constant time, even though individual appends can occasionally be much slower.

scores = [85, 92, 78, 90]
print(scores[0])     # 85 — first element, index 0
print(len(scores))    # 4  — number of elements

name = "hello"
print(name[1])          # 'e' — second character, index 1