المصفوفات الديناميكية وتغيير الحجم

Written Explanation

Plain array plus a counter

A dynamic array has two pieces of state:

private Object[] data = new Object[4];   // the lockers
private int size;                          // how many are really used

• Capacity is data.length: how many items fit before the array is full.
• Size is size: how many items are actually stored.

Always size <= capacity. The spare lockers are the room to grow into. Appending a new item has two cases:

1. size < capacity: write at data[size] and increase size. One write, O(1).
2. size == capacity: the array is full. Make a bigger one, copy, then write.

The resize step

if (size == data.length) {
    data = java.util.Arrays.copyOf(data, data.length * 2);
}
data[size++] = item;

Arrays.copyOf(original, newLength) returns a new array of the given length. It keeps the old items in order and fills any extra slots with defaults, which for an array of objects means null. The old array is no longer referenced by data, so the garbage collector can reclaim it later. Copying size items costs O(n). Everything else in add is O(1).

Why not grow by one?

Imagine a stricter rule: when full, grow to data.length + 1. After the first full array, every append finds the array full, so every append copies everything. If the list is n items long, copying costs roughly 1 + 2 + 3 + ... + n, which is about n²/2: O(n²) in total.

With doubling, you only copy when the capacity is exhausted, and each copy buys you as many free appends as there are items. The total copying over n appends is below about 2n items, so the average cost per append is a constant.

The numbers below come from a real run (start capacity 4):

Doubling stays close to n items moved; +1 explodes. This is the "resize by +1 instead of doubling" mistake listed for this module.

Amortized O(1)

Amortized cost means the average cost per operation, taken over a whole sequence of operations, in the worst case for that sequence. It is not a probability and not "usually". Here is the argument in plain words, for doubling from capacity c:

• Resizes happen at sizes c, 2c, 4c, ... Each copies that many items.
• Adding those up: c + 2c + 4c + ... + n/2 is less than n, because each term is half of the next.
• So n appends cost about n writes plus fewer than n copied items: under roughly 2n steps in total.
• Divide by n appends: a small constant per append.

The Java documentation for ArrayList states this contract for add: it runs in amortized constant time, meaning adding n elements takes O(n) time. The same page says the details of the growth policy are not specified, so you cannot rely on ArrayList growing by exactly 2x. Your own MyArrayList in the lab will double because you choose to.

Worst case is still O(n)

"Amortized O(1)" is a statement about the total, not about every call. The one append that triggers a resize copies every item and is O(n). Over a million appends that happens about 20 times, so the average is tiny, but a single request that hits the resize may be slower than its neighbours. In backend terms: average throughput is great; the occasional slow call is the price. If you know the final size ahead of time, you can avoid the surprise by creating the list with a suitable initial capacity (new ArrayList<>(10_000)) so no resize happens.

Capacity grows, but does it shrink?

In this lesson's simple version, no. After a remove, size goes down, but the array keeps its length. That is a deliberate simplicity; real libraries make their own choices. For your own class, the important rule from the demo lesson is to clear the freed slot (data[size] = null) so the removed object is not kept alive by a stale reference.