An **ArrayList** (or dynamic array) is a resizable, list-like data structure that provides fast random
access to elements and dynamically adjusts its capacity as elements are added or removed. Here's a
clear breakdown:
---
### **1. Core Concept**
- **Underlying Structure**: Internally uses a **contiguous array** to store elements.
- **Dynamic Sizing**: Automatically grows/shrinks its capacity when elements are added/removed
(unlike fixed-size arrays).
- **Order Preservation**: Maintains the insertion order of elements.
---
### **2. Key Operations**
| **Operation** | **Description** | **Time Complexity** |
|----------------------------|---------------------------------------------------------------------------------|---------------------|
| **Add Element** | Append to the end (amortized O(1)); insert at index (shifts elements, O(n)).
| O(1) / O(n) |
| **Remove Element** | Remove by value or index (shifts elements, O(n)). | O(n)
|
| **Get/Set Element** | Access or modify an element by index (direct via array pointer). |
O(1) |
| **Search** | Check if an element exists (linear scan). | O(n) |
| **Resize** | Allocate a new array and copy elements when capacity is exceeded. |
O(n) |
---
### **3. How It Works**
- **Initial Capacity**: Starts with a default size (e.g., 10 in Java’s `ArrayList`).
- **Resizing Strategy**:
- When full, it creates a new array (usually **double the size**) and copies existing elements.
- This resizing is expensive (O(n)) but happens infrequently, leading to **amortized O(1)** time for
appends.
- **Shrinking**: Some implementations reduce capacity when elements are removed (optional).
---
### **4. Pros and Cons**
| **Advantages** | **Disadvantages** |
|-----------------------------------------|--------------------------------------------|
| Fast O(1) random access by index. | Insertions/deletions in the middle are slow (O(n)) due to
shifting. |
| Memory-efficient (contiguous memory). | Wasted space if capacity exceeds needs. |
| Easy to implement and use. | Resizing can cause occasional latency. |
---
### **5. ArrayList vs. Linked List**
| **ArrayList** | **Linked List** |
|------------------------------------------|---------------------------------------------|
| Fast access by index (O(1)). | Slow access by index (O(n)). |
| Slow insertions/deletions in the middle. | Fast insertions/deletions (O(1) for nodes). |
| Memory-efficient (no pointers). | Extra memory for node pointers. |
---
### **6. Example in Code (Pseudocode)**
```python
# Create an ArrayList
list = ArrayList()
# Add elements
[Link](10) # [10]
[Link](20) # [10, 20]
[Link](1, 15) # [10, 15, 20] (shifts elements)
# Access element
print([Link](1)) # Output: 15
# Remove element
[Link](15) # [10, 20] (shifts elements)
# Check size
print([Link]()) # Output: 2
```
---
### **7. When to Use an ArrayList**
- You need **fast access** to elements by index.
- The list size changes frequently, but **add/remove operations are mostly at the end**.
- Memory efficiency is important (better than linked lists for small elements).
---
### **8. Implementations in Popular Languages**
- **Java**: `[Link]`
- **Python**: Built-in `list` (dynamic array)
- **C++**: `std::vector`
- **C#**: `List<T>`
---
### **Summary**
An **ArrayList** is ideal for scenarios requiring frequent **random access** and **ordered data**, but
it trades off slower insertions/deletions in the middle. It’s a foundational structure in most programming
languages and a go-to choice for many use cases.