Micro-questions over the dynamic arrays module. Answer each one out loud in a full sentence before opening the toggle; mark yourself got it / close / blank. Format explained in the arrays bank.


A. The object itself

1. What is a dynamic array?

Answer

An array that can grow. Underneath it is still a plain fixed-size array — the growing is a trick played on top of it.

2. What is it called in Python, JavaScript, C++ and Java?

Answer

Python list, JavaScript Array, C++ std::vector, Java ArrayList. Also called a resizable array.

3. Why do dynamic arrays exist? What problem do they solve?

Answer

You almost never know in advance how many items you will need — records loaded, items in a cart, messages off a socket. A static array demands its size at creation; a dynamic array manages capacity for you.

4. Give a real-world illustration.

Answer

An expandable accordion suitcase. Compact while it fits; unzip the extension seam to double its capacity when you run out of room.

5. What does a dynamic array keep that a plain array does not?

Answer

Two numbers instead of one: length (how many elements are stored) and capacity (how many the block could hold).


B. The vocabulary

6. What is length?

Answer

How many elements are actually stored right now — the number len() returns.

7. What is capacity?

Answer

How many elements the underlying memory block could hold before running out. Usually larger than the length, and invisible from outside.

8. What is headroom?

Answer

The spare space, capacity - length. It is what lets an append happen with no copying, and the whole reason appends are usually instant.

9. What is the growth factor?

Answer

The multiplier used when the block runs out of room — commonly , sometimes . That it is a multiplier and not a fixed amount is the single most important detail about it.

10. What is reallocation?

Answer

The expensive step: request a bigger block, copy every existing element into it, release the old block. , and the thing you are trying to do rarely.

11. What does amortised mean?

Answer

A single operation can occasionally be slow, but the average cost across a long run of operations is constant. It is a statement about the total, never a promise about any one call.


C. How resizing actually works

12. What triggers a resize?

Answer

An append when length == capacity — there is no headroom left.

13. Name the four steps of a resize, in order.

Answer
  1. Allocate a new block with double the capacity.
  2. Copy every existing element into it.
  3. Free the old block.
  4. Write the new element.

14. After appending to a full array of length = capacity = 4, what are the new length and capacity?

Answer

length = 5, capacity = 8 — three headroom slots left, which is why the next three appends are instant.

15. Why can’t the array just extend the existing block in place?

Answer

The memory immediately after the block is not owned by the array and is very likely already in use by something else. Contiguity can only be guaranteed by finding a fresh block big enough.

16. Does resizing change any element’s index?

Answer

No. Indices are unchanged; only the addresses change, because the base address moved. Any raw pointer into the old block is now dangling — which is why C++ says iterators are invalidated by a push_back that reallocates.


D. The amortised argument

17. A single resize costs . So why is append called ?

Answer

Because capacity doubles, resizes get exponentially rarer as the array grows. The rare expensive calls are spread over an ever-larger number of cheap ones.

18. Appending 16 elements from capacity 1, how many copies happen in total?

Answer

copies.

19. Write the general sum for appends and evaluate it.

Answer

A geometric series whose terms double sums to just under twice the last term.

20. Total work for appends, and therefore the average cost per append?

Answer

insertions + fewer than copies operations, so — a constant, i.e. amortised.

21. Why does growing by a fixed amount (say +10 slots) fail?

Answer

Resizes then happen every 10 appends no matter how big the array is, and each copies everything. Total copy work becomes , so append degrades to on average.

22. State the difference between doubling and +10 in one sentence.

Answer

Doubling makes the gap between resizes grow with the array; adding a constant keeps the gap fixed while the cost of each resize grows — so one sums to and the other to .

23. Is a growth factor of 1.5 still amortised ?

Answer

Yes. Any factor strictly greater than 1 gives a geometric series and therefore amortised ; 1.5 simply trades a little more copying for less wasted memory. (It also allows freed blocks to be reused, which is why some allocators prefer it.)


E. Costs

24. Cost of access by index?

Answer

— the storage is still one contiguous block, so the address arithmetic from arrays is unchanged.

25. Cost of append at the end?

Answer

amortised; worst case on the rare resize.

26. Cost of pop from the end?

Answer

— decrement the length counter; nothing shifts.

27. Cost of insert or delete at the front?

Answer

— every subsequent element must shift. Dynamic arrays solved the sizing problem, not the shifting problem.

28. Cost of searching an unsorted dynamic array?

Answer

— a linear scan, exactly as for a plain array.


F. The ADT

29. What does the dynamic array ADT add to the plain array ADT?

Answer

append, pop, insert(i, v) and delete(i) — the operations a fixed array cannot have because its length is frozen at creation.

30. Which two ADT operations are , and why is that unavoidable?

Answer

insert(i, v) and delete(i). Contiguous storage means there is no gap to insert into and no way to close a hole, so elements must physically move.


G. The precise claim, and where it bites

31. Why is “appending is ” a statement about a sequence rather than a call?

Answer

Any individual append may be the unlucky one that copies a million elements. The average over the sequence is constant; no single call is guaranteed to be.

32. Where does that occasional spike actually matter?

Answer

Latency-sensitive code — an audio callback, a control loop, a game frame. Your average looks perfect and your worst-case timing still blows the budget.

33. What is the fix when it matters?

Answer

Reserve capacity up front: reserve() in C++, ensureCapacity() in Java, [None] * n in Python. If no resize can happen, no spike can happen.

34. Why is pre-allocation an optimisation even when latency doesn’t matter?

Answer

It removes every resize copy. Building a 100,000-item list by repeated append does roughly 100,000 extra element copies that pre-allocation skips entirely.

35. Why does Python not expose reserve()?

Answer

It deliberately hides capacity as an implementation detail. That is one reason building a list in a hot loop by repeated append is sometimes replaced by preallocating a list of the right size and assigning by index.


H. Boundaries and comparisons

36. Does a dynamic array ever shrink?

Answer

Some implementations do, when length falls well below capacity. The threshold is deliberately not half — shrinking at exactly half lets repeated append/pop at the boundary thrash, resizing on every call. Shrinking at a quarter gives hysteresis that prevents it.

37. How much memory can a dynamic array waste?

Answer

Up to nearly half its block under doubling, just after a resize. That wasted headroom is exactly what is bought with the append — space traded for time.

38. You need fast insertion at the front. What do you use?

Answer

A linked list, or a deque / queue — a ring buffer gives at both ends while keeping contiguous storage.

39. Is a Python list contiguous?

Answer

Its pointer slots are contiguous; the objects pointed at are scattered. So indexing is but cache locality is weaker than a true array of values (array.array, NumPy).

40. In one sentence, what is a dynamic array?

Answer

A plain array plus a capacity counter and a doubling rule — which buys append at the price of occasional copying and some wasted space.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Data Structures — University-Style Teaching Notes