Arrays, Dynamic Arrays, and Strings as Sequential Data
Why fixed-size arrays give O(1) index access, how a dynamic array grows without becoming O(n) per insert, and strings as a special case of the same sequential-access tradeoffs.
What you'll learn
- Explain why array index access is O(1) but insertion in the middle is O(n)
- Explain how a dynamic array achieves O(1) amortized append despite occasional resizing
- Choose between an array-backed structure and alternatives based on the operations a problem actually needs
Prerequisites
Explanation
A fixed-size array stores its elements in one contiguous block of memory, which is exactly what makes arr[i] an O(1) operation: the address of element i is computed directly (baseAddress + i * elementSize), with no searching required, regardless of how large the array is. That same contiguous layout is what makes insertion in the middle expensive: inserting at index k requires shifting every element from k onward one position to make room — an O(n) operation in the worst case (inserting at the front), because up to n elements might need to move. Removing from the middle has the same O(n) cost, for the same reason: closing the gap means shifting everything after it back by one.
A dynamic array (JavaScript's Array, Java's ArrayList, Python's list) is a fixed-size array under the hood, plus logic to transparently replace it with a larger one when it fills up. When .push() is called on a full backing array, the implementation allocates a new array — typically double the previous capacity, not just one element more — copies every existing element across, and only then adds the new one. That doubling strategy is the entire trick behind the earlier lesson's amortized-analysis claim: resizes become exponentially rarer as the array grows (you double from 4 to 8, 8 to 16, 16 to 32...), so the total cost of all the copying, spread proportionally across every .push() call in between, averages out to O(1) per call — even though any single call that happens to trigger a resize is genuinely O(n) for that one call.
Strings, in most languages including JavaScript, behave like a specialized, immutable array of characters: indexing a character is O(1), but because strings are immutable, any "modification" (concatenation, replacing a substring) must allocate an entirely new string, copying the unchanged parts — which is why building a large string by repeatedly concatenating in a loop is O(n²) overall (each of the n concatenations copies an ever-growing string), while collecting pieces in an array and joining once at the end is O(n) overall. This is the exact same underlying tradeoff — contiguous, fixed-size storage traded against fast random access — showing up in a second, extremely common context.
Example
Amortized O(1) append vs. the O(n) cost of a middle insertion, made visible by counting shifted elements.
function insertAt(arr, index, value) {
let shifts = 0;
arr.push(undefined); // make room at the end
for (let i = arr.length - 1; i > index; i--) {
arr[i] = arr[i - 1]; // shift each element right by one
shifts++;
}
arr[index] = value;
return shifts;
}
const data = [1, 2, 3, 4, 5];
console.log(insertAt(data, 4, 99)); // inserting near the END: few shifts
console.log(insertAt([1, 2, 3, 4, 5], 0, 99)); // inserting at the FRONT: shifts every element -- O(n)Try it yourself
Try inserting at the middle index (2) of a 6-element array and compare the shift count to front and back insertion.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write buildStringWithArray(parts) that joins an array of string parts efficiently (O(n) total): use array push/join, NOT string += concatenation in a loop. Then write buildStringNaively(parts) using += concatenation, to compare -- both must produce the identical final string.
Checks: array-based building produces the correct string · naive concatenation produces the same, correct string · handles an empty parts array
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write countShiftsForFrontInsert(n) returning the number of element shifts required to insert one element at the FRONT of an n-element array (should equal n), and countShiftsForBackInsert(n) returning the shifts required to append at the back (should always be 0, regardless of n).
Checks: front insertion shift count scales with n · front insertion into an empty array needs 0 shifts · back insertion never needs shifts, regardless of array size
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Repeatedly inserting at the front of a large array in a loop, not realizing each insertion is O(n) -- this silently turns an intended O(n) algorithm into O(n^2) overall.
- Building a large string with += inside a loop -- each concatenation allocates a new string and copies everything so far, making the total cost O(n^2), not O(n).
- Assuming .push() is always instantaneous -- it's O(1) AMORTIZED, meaning most calls are cheap but an occasional call (when the backing array must grow) is genuinely O(n) for that one call.
Knowledge check
Takeaway
Contiguous storage gives arrays O(1) index access at the cost of O(n) middle insertion/removal; a dynamic array's doubling strategy makes .push() O(1) amortized even though any individual resize is O(n); strings share the exact same tradeoffs because they're effectively immutable character arrays.
Summary
Array index access is O(1); inserting or removing in the middle is O(n) due to shifting. Dynamic arrays double their capacity to keep .push() O(1) amortized. Strings are immutable arrays of characters — build large strings by collecting pieces and joining once, not by repeated concatenation.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.