 (36).png)
Custom Implementation of ArrayList in Java
Building a Dynamic Array from Scratch
Introduction
The ArrayList is one of the most widely used data structures in Java’s Collections Framework.
It is a resizable array implementation, which means it can dynamically grow or shrink as elements are added or removed.
Unlike arrays, which have a fixed size, ArrayList offers:
- Dynamic resizing
- Easy indexing
- Rich set of methods for manipulation
In this blog, we will:
- Understand how ArrayList works internally.
- Learn about its dynamic resizing mechanism.
- Implement a custom ArrayList from scratch.
- Analyze its pros, cons, and practical applications.
Internal Working of ArrayList
ArrayList is backed by a resizable array (Object[] elementData).
Key operations involve:
- Index-based access (O(1) time).
- Dynamic resizing (copying to a larger array when capacity is exceeded).
- Shift operations when adding/removing in the middle.
Key Points:
- Default initial capacity is 10.
- When capacity is exceeded, ArrayList grows by 50% of the current size (in Java’s implementation).
- It uses modCount to keep track of structural modifications.
Designing a Custom ArrayList
We will now build a simplified version of ArrayList.
Step 1: Define the CustomArrayList Class
public class CustomArrayList {
private Object[] data;
private int size;
private int capacity;
public CustomArrayList() {
capacity = 10;
data = new Object[capacity];
size = 0;
}
}
Here:
- data is the underlying array.
- size tracks the number of elements.
- capacity is the allocated length of the array.
Step 2: Implement the add() Method
public void add(T element) {
if (size == capacity) {
grow();
}
data[size++] = element;
}
Step 3: Implement the grow() Method
Resizes the array when capacity is exceeded.
private void grow() {
capacity = capacity + (capacity >> 1); // increase by 50%
Object[] newData = new Object[capacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
Step 4: Implement the get() Method
public T get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
return (T) data[index];
}
Step 5: Implement the remove() Method
public T remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
T removedElement = (T) data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
data[size - 1] = null;
size--;
return removedElement;
}
Step 6: Implement the size() Method
public int size() {
return size;
}
Step 7: Implement the display() Method
public void display() {
for (int i = 0; i < size; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
Step 8: Testing CustomArrayList
public class TestCustomArrayList {
public static void main(String[] args) {
CustomArrayList list = new CustomArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");
list.add("Go");
list.display();
System.out.println("Element at index 2: " + list.get(2));
list.remove(1);
list.display();
System.out.println("Size: " + list.size());
}
}
Expected Output
Java Python C++ Go
Element at index 2: C++
Java C++ Go
Size: 3Complete CustomArrayList Implementation
// CustomArrayList Implementation
public class CustomArrayList<T> {
private Object[] data;
private int size;
private int capacity;
// Constructor
public CustomArrayList() {
capacity = 10;
data = new Object[capacity];
size = 0;
}
// Add element to list
public void add(T element) {
if (size == capacity) {
grow();
}
data[size++] = element;
}
// Resize array by 50%
private void grow() {
capacity = capacity + (capacity >> 1); // increase capacity by 50%
Object[] newData = new Object[capacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
// Get element at index
@SuppressWarnings("unchecked")
public T get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
return (T) data[index];
}
// Remove element at index
@SuppressWarnings("unchecked")
public T remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
T removedElement = (T) data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
data[size - 1] = null;
size--;
return removedElement;
}
// Get current size
public int size() {
return size;
}
// Display elements
public void display() {
for (int i = 0; i < size; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
}
Testing the CustomArrayList
public class TestCustomArrayList {
public static void main(String[] args) {
CustomArrayList<String> list = new CustomArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");
list.add("Go");
list.display(); // Java Python C++ Go
System.out.println("Element at index 2: " + list.get(2)); // C++
list.remove(1); // removes "Python"
list.display(); // Java C++ Go
System.out.println("Size: " + list.size()); // Size: 3
}
}
✅ Expected Output:
Java Python C++ Go
Element at index 2: C++
Java C++ Go
Size: 3
Time Complexity of ArrayList Operations
| Operation | Time Complexity |
|---|---|
| add(element) | O(1) (amortized) |
| get(index) | O(1) |
| remove(index) | O(n) |
| contains() | O(n) |
Differences Between Array and ArrayList
| Feature | Array | ArrayList |
|---|---|---|
| Size | Fixed | Dynamic |
| Memory Allocation | Static | Dynamic |
| Methods | Limited | Rich API |
| Performance | Faster access | Slightly slower due to resizing |
| Generics Support | No | Yes |
Advantages of ArrayList
- Dynamic resizing without manual memory management.
- Easy indexing and iteration.
- Rich API for element manipulation.
- Supports generics.
Disadvantages of ArrayList
- Slower insertion/removal in the middle due to shifting.
- Extra memory used for resizing.
- No built-in synchronization (use Collections.synchronizedList() if needed).
Real-World Applications
- Storing data that changes in size dynamically.
- Implementation of stacks, queues.
- Backing structure for more complex data structures (like HashMap values, etc.).
- Use in algorithms where frequent random access is needed.
Conclusion
In this blog, we built a CustomArrayList to understand:
- How dynamic resizing works.
- How indexing and shifting happen internally.
- Why ArrayList offers both flexibility and performance.
This implementation gave us insight into how ArrayList balances speed and memory efficiency in Java.
Next Blog- How Iterators Work in Java Collections
 (17).png)
.png)
 (53).png)
 (18).png)
.png)
.png)
 (1).png)
 (2).png)
 (3).png)
 (4).png)
 (5).png)
 (6).png)
 (9).png)
 (7).png)
 (10).png)
 (8).png)
 (10).png)
 (12).png)
 (13).png)
 (13).png)
 (15).png)
 (16).png)
 (19).png)
 (20).png)
 (21).png)
 (22).png)
 (23).png)
 (24).png)
 (25).png)
 (26).png)
 (27).png)
 (28).png)
 (29).png)
 (30).png)
 (31).png)
 (32).png)
 (54).png)
 (33).png)
 (34).png)
 (35).png)
 (37).png)
 (38).png)
 (39).png)
 (40).png)
 (41).png)
 (42).png)
 (45).png)
 (46).png)
 (47).png)
 (48).png)
 (55).png)
 (50).png)
 (51).png)
 (52).png)
 (56).png)
.png)
 (44).png)
