Arrays & dynamic arrays

An array is a block of memory split into equal-sized slots, one per element, stored one after another. Because every slot has the same size, the address of element i is simply start + i times slot size, so reading or writing any index takes the same constant time.

A fixed array cannot grow. A dynamic array (Python list, Java ArrayList, C++ vector, Go slice, JavaScript array) keeps a fixed array underneath with some spare capacity. When it fills up, it allocates a bigger block, copies everything over and frees the old one. Because the capacity grows by a multiple each time, the copying cost averages out to O(1) per append.

1. 1Read or write by index: compute start + i times slot size and jump there. This is O(1) and does not depend on the array's length.
2. 2Append: if there is spare capacity, write into the next free slot and increase the length. O(1).
3. 3Append when full: allocate a new block, usually 1.5x to 2x bigger, copy all n elements, then append. That single append costs O(n), but it happens rarely.
4. 4Amortized cost: with doubling, the copies over n appends add up to at most about 2n (1 + 2 + 4 + ... + n), so the average cost per append is O(1).
5. 5Insert or delete at position i: every element after i must shift one slot right or left, so the cost is O(n - i), which is O(n) in the worst case. Removing the last element is O(1).
6. 6Search for a value in an unsorted array means checking each slot: O(n). If the array is sorted, binary search finds it in O(log n).

class DynamicArray:
    def __init__(self):
        self.cap = 1                  # slots allocated
        self.n = 0                    # slots in use
        self.data = [None] * self.cap

    def get(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)
        return self.data[i]           # O(1): base + i * slot size

    def append(self, x):
        if self.n == self.cap:        # full: double the capacity
            self._resize(2 * self.cap)
        self.data[self.n] = x
        self.n += 1

    def pop(self):
        if self.n == 0:
            raise IndexError("pop from empty array")
        self.n -= 1
        x, self.data[self.n] = self.data[self.n], None
        return x

    def _resize(self, new_cap):
        new = [None] * new_cap
        for i in range(self.n):       # O(n) copy, but rare
            new[i] = self.data[i]
        self.data, self.cap = new, new_cap

A minimal dynamic array. get() is O(1) because it indexes directly. append() is O(1) except when the array is full; then _resize() copies everything into a block twice the size. Because the capacity doubles, total copying over n appends is under 2n, so append is amortized O(1). pop() from the end is O(1).

Cost: Access O(1). Append amortized O(1), worst case O(n). Insert or delete at index i O(n - i). Pop from end O(1). Search O(n) unsorted, O(log n) sorted. Space O(n), with up to a constant factor of spare capacity.