Arrays & strings

An array stores its items next to each other in one block of memory, and every item takes the same number of bytes. An item's position is its index, counted from 0: the first item is a[0], the fourth is a[3].

Because the items are packed and equal in size, the computer never has to walk the array to find one. It works out where item i lives:

address of a[i] = start of the block + i × size of one item

That is one multiplication and one addition, whether the array holds four items or four million. Reading or writing a[i] costs O(1).

The table is an array of four whole numbers, 4 bytes each, starting at address 1000. Item 3 is at 1000 + 3 × 4 = 1012. This is also why indexes start at 0: the index is how many items you skip from the start.

The price of this layout is that the block is one piece. There is no room between two neighbors, and the block has a fixed size, chosen when it is created. The next three sections are about what that costs.

Say the array holds 3, 8, 1, 5 and has one free cell at the end. You want 9 at index 1, between 3 and 8. There is no gap there, so you have to make one: every item from index 1 onward moves one cell to the right, and then 9 goes into the cell that opened up.

The moves run from the end backward. If you went left to right, copying 8 into index 2 would overwrite the 1 before it had moved anywhere.

Inserting at index i into n items moves n − i of them:

• at the front (i = 0), all n items move;
• in the middle, about half of them;
• at the end (i = n), none do, as long as there is a free cell.

Deleting the item at index i leaves a hole, and an array can't have holes: its items must stay packed for the address rule to work. So every item after i moves one cell to the left. This time the moves run from the hole forward, so each item is copied before its own cell is overwritten.

The last cell ends up holding a copy of the item before it, so the code clears it and the array's length drops by one. Like insertion, deleting at the front moves everything, and deleting at the end moves nothing.

When the order of the items doesn't matter (a bag of tasks, a set of players), there is a faster way: move the last item into the hole and shorten the array by one. That is one copy instead of n − i, so it costs O(1).

The block can't simply get longer, because the memory right after it may already belong to something else. A dynamic array (Python's list, Java's ArrayList, C++'s std::vector) handles this by keeping some spare cells. Its capacity is how many cells the block has; its length is how many are in use.

Appending while there is spare capacity is one write: O(1). When the block is full, the next append has to do more work:

A copy of every item sounds expensive, and that one append is. But because the capacity grows by a multiple, the copies get rarer as the array grows, and spread over all the appends they add only a constant amount to each. Appending is O(1) on average, or amortized. Space & amortized analysis works through why.

A string is a sequence of characters stored like an array, so s[i] is a constant-time lookup and length of s is known without counting.

One caveat about what a "character" is. Java and JavaScript store strings as UTF-16, and their length counts 16-bit code units. Most characters take one unit, but an emoji or a rarer script takes two, so "😄".length is 2 and an index can land on half of one. Python indexes whole characters (code points).

In Java, Python and JavaScript, strings are immutable: once created, a string never changes. Code that seems to change one, like s ← s + c, builds a new string and copies both parts into it. In a loop, that copying adds up.

Building a string of n characters one at a time copies 1 + 2 + … + n = n(n + 1) ÷ 2 characters: about 50 million for a 10,000-character string. That is O(n²) for a job that should be O(n).

The fix is to collect the pieces in something you can change and turn it into a string once at the end:

Some runtimes speed up repeated + in special cases, but the language doesn't promise it, so don't count on it.

The table undersells one thing: arrays are fast in practice even when you visit every item. The processor fetches memory in small blocks (cache lines), so reading one item brings its neighbors along, and walking an array front to back is about the friendliest thing you can ask of the hardware.

Arrays are the right default for most lists. When a job needs many inserts and deletes in the middle, Linked lists trade the shifting for slower lookups by index.