Array
An array is the most fundamental data structure. It stores elements in a contiguous block of memory, and each element is accessed through an index (position) starting from 0.
Static Array
A static array has a fixed size at declaration. In Python, a list behaves like a dynamic array that resizes automatically.
# Static array in Java
# int[] arr = new int[5]; // fixed size of 5
# Dynamic array in Python
arr = [10, 20, 30, 40, 50]
print(arr[0]) # 10 (access index 0)
print(arr[2]) # 30 (access index 2)
Dynamic Array
A dynamic array automatically grows its capacity when it is full. Python's list is an example of a dynamic array.
arr = [1, 2, 3]
arr.append(4) # [1, 2, 3, 4]
arr.insert(1, 10) # [1, 10, 2, 3, 4]
arr.pop() # [1, 10, 2, 3]
arr.remove(10) # [1, 2, 3]
Operations and Time Complexity
| Operation | Time | Notes |
|---|---|---|
| Access (by index) | O(1) | Jumps directly to the memory address |
| Search | O(n) | Must traverse one element at a time |
| Insert at end | O(1) amortized | May require a resize |
| Insert in middle | O(n) | Shifts the elements after it |
| Delete at end | O(1) | Simply remove it |
| Delete in middle | O(n) | Shifts the elements after it |
Python List vs Java Array
| Feature | Python List | Java Array |
|---|---|---|
| Data types | Heterogeneous | Homogeneous |
| Size | Dynamic | Static |
| Resize | Automatic | Manual (copy to a new array) |
| Built-in methods | Many | Few |
# A Python list can mix types
mixed = [1, "hello", 3.14, True]
# A Java array must be a single type
# int[] nums = {1, 2, 3};
# String[] names = {"a", "b"};
When to Use an Array
Use an array when:
- You need fast access by index
- The data size is relatively stable
- You need sequential iteration
Avoid an array when:
- You frequently insert/delete in the middle
- The size is highly unpredictable
Got the hang of arrays? Now let's study the Linked List, which is more flexible for insert and delete operations.