index 0
10
Understand dynamic arrays, Java ArrayList, Python list, resizing, capacity, operations and the interview patterns built on top of them.
A dynamic array behaves like an array but can grow when more elements are needed.
When capacity is reached, a larger backing array can be allocated and elements copied over.
Index-based access is O(1) because elements live in contiguous array storage.
Adding at the end is usually amortized O(1), with occasional O(n) resizing.
Both provide dynamic-array behavior, but the APIs and implementation details differ.
| Feature | Java ArrayList | Python list |
|---|---|---|
| Type | Dynamic implementation of List | Built-in mutable sequence |
| Index access | O(1) | O(1) |
| Append | Amortized O(1) | Amortized O(1) |
| Insert at beginning | O(n) | O(n) |
| Remove from middle | O(n) generally | O(n) generally |
| Duplicates | Allowed | Allowed |
| Random access | Yes | Yes |
This distinction is the key to understanding dynamic arrays.
Add at the end. Usually amortized O(1).
Read by index in O(1).
Replace a value by index in O(1).
Removing can require shifting, so generally O(n).
| Operation | Complexity | Reason |
|---|---|---|
| Access by index | O(1) | Direct indexing |
| Append | Amortized O(1) | Occasional resize is spread over many appends |
| Insert middle | O(n) | Elements may need to shift |
| Remove middle | O(n) | Elements may need to shift |
| Search by value | O(n) | May scan all elements |
Important!!
Part 1.
Part 2.
Prepare for common interview questions.
Prepare for common interview questions.
Prepare for common interview questions.
Prepare for common interview questions.
Core Concept.