Dynamic Arrays

# CHAPTER 4

Dynamic Arrays #

1. Introduction #

2. Learning Objectives #

• Define the difference between *Capacity* and *Size*.

• Understand the algorithmic process of Array Resizing.

• Understand Amortized Time Complexity.

• Write custom logic to simulate a Dynamic Array in static languages.

3. The Core Concept: Size vs. Capacity #

• Size (or Length): The number of elements actually pushed into the array by the user.

• Capacity: The physical number of memory slots currently reserved by the operating system.

Visualizing the Trick:

Array: [10] [20] [30] [Empty] [Empty]
Size: 3 (We only placed 3 items)
Capacity: 5 (The physical memory can hold up to 5)

When you push a 4th item, it goes into the empty slot. It is instantaneous O(1). But what happens when the Capacity fills up?

4. The Resizing Algorithm #

The 4 Steps of Resizing:

1. 1. Allocate: The engine creates a brand new, empty static array in memory that is *double* the capacity of the old one (e.g., from 5 to 10).

1. 2. Copy: The engine runs an O(n) loop to copy every single element from the old array into the new array.

1. 3. Swap: The internal pointer of the array object is switched to point to the new, larger array.

1. 4. Destroy: The old, small array is deleted from memory (Garbage Collection).

5. Implementing a Dynamic Array (Mental Model) #

// C++ Example: The mechanics of std::vector
#include <iostream>
using namespace std;

class MyDynamicArray {
private:
    int* arr;
    int capacity;
    int size;

public:
    MyDynamicArray() {
        capacity = 2; // Start small
        size = 0;
        arr = new int[capacity]; // Allocate physical static array
    }

    void push(int element) {
        if (size == capacity) {
            // TRIGGER RESIZE: Double the capacity!
            int newCapacity = capacity * 2;
            int* newArr = new int[newCapacity];
            
            // O(n) COPY OPERATION
            for (int i = 0; i < size; i++) {
                newArr[i] = arr[i];
            }
            
            delete[] arr; // Destroy old array
            arr = newArr; // Swap pointers
            capacity = newCapacity;
            cout << "Array resized to capacity: " << capacity << endl;
        }
        
        // O(1) Insertion
        arr[size] = element;
        size++;
    }
};

int main() {
    MyDynamicArray list;
    list.push(10); // Size 1, Cap 2
    list.push(20); // Size 2, Cap 2
    list.push(30); // Size 3, Cap 4 (Triggers resize!)
    return 0;
}

6. Amortized Time Complexity #

7. Language Implementations #

• Java (ArrayList): Grows by 50% (Capacity * 1.5).

• C++ (std::vector): Grows by 100% (Capacity * 2).

• Python (list): Uses a complex formula, roughly growing by 112%. Python lists are actually dynamic arrays of pointers, not raw data!

8. Memory Waste (The Tradeoff) #

9. Common Mistakes #

• Pre-allocating poorly: In Java or C++, if you know you are going to push 10,000 items into a list, doing new ArrayList<>() will cause the array to resize and copy itself dozens of times during execution, slowing down your program. Always set an initial capacity: new ArrayList<>(10000).

10. Best Practices #

• Shrinking: Just as arrays grow, they should shrink. If you delete 90% of the elements in a dynamic array, most standard libraries will trigger a "Shrink" event, cutting the capacity in half to return the wasted RAM back to the operating system.

11. Exercises #

1. 1. If a dynamic array currently has a size of 4 and a capacity of 4, and it is programmed to double its capacity on resize, what will be the capacity after inserting 3 more elements?

1. 2. Explain the difference between size() and capacity() in a C++ std::vector.

12. MCQs with Answers #

13. Interview Preparation #

• *System Design:* "Explain the internal architectural mechanics of a Java ArrayList or Python list. Describe the exact lifecycle of memory allocation, resizing, copying, and garbage collection when the structure reaches maximum capacity."

• *Conceptual:* "Define 'Amortized Time Complexity' and explain mathematically why inserting an element at the end of a Dynamic Array is considered O(1) despite the existence of the O(n) resize operation."

Common Pitfalls:

• In an interview, if you are asked to design a real-time system (like trading software or medical device software) where "stutters" or "pauses" are completely unacceptable, do NOT use a Dynamic Array. The rare O(n) resize operation will cause a microsecond CPU freeze.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #