Card 09/ 09
Recap: Arrays and Strings
Index reads are instant, shifts are linear, growth is amortised, and strings are rebuilt.
Arrays and Strings comes down to the seven ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| Elements sit in adjacent cells of one size, so the cell at index i is at base + i × size and a read is O(1) | Arrays: Contiguous Cells Read by Index |
| A grid stored row by row puts row r, column c at index r × columns + c | Compute an Element's Address in One and Two Dimensions |
| Inserting at index i shifts the n − i elements after it, so an insert at the front moves all n | Array Example: Inserting at the Front |
| A dynamic array doubles its capacity when full, so n appends copy fewer than 2n elements | Dynamic Arrays and Amortised Growth |
| Judge an operation called many times by its total divided by the calls, not by its slowest call | Judging Append by Its Slowest Call |
| Python's list, Java's ArrayList and a TypeScript array are dynamic arrays with different growth factors | Dynamic Array in Python, Java and TypeScript |
| Adding to a string in a loop is O(n²) in the pieces; collecting them and joining once is O(n) | String Building Example: Joining a Thousand Words |
The operations table for a fixed array gains two rows for the dynamic array, because its append has two costs worth naming.
| Operation | Cost | Case | Why |
|---|---|---|---|
| Read by position | O(1) | worst | One multiplication and one addition find the cell |
| Search by value | O(n) | worst | Every cell may be checked |
| Insert at index i | O(n) | worst | Every element from i onwards moves one cell right |
| Delete at index i | O(n) | worst | Every element after i moves one cell left |
| Append to a dynamic array | O(1) | amortised | Copies over n appends add up to less than 2n |
| The append that resizes | O(n) | worst | Every element is copied into the larger block |
Together they let you choose an array where reading by position matters, and see the cost before a loop inserts at the front or adds to a string.
← → move through sections and cards