How to Implement Your Own Array List in Java

Introduction

Have you ever wondered how Java’s ArrayList works under the hood? While the standard ArrayList is efficient and easy to use, building your own version from scratch can significantly enhance your understanding of data structures, memory management, and Java programming in general.

In this blog post, we’ll walk step by step through implementing a custom ArrayList in Java, covering its core features such as dynamic resizing, adding, removing, and accessing elements. By the end, you’ll have a solid grasp of how ArrayList operates and the confidence to experiment with other custom data structures.

Prerequisites

Before diving in, make sure you’re familiar with:

• Basic Java programming concepts.

• Arrays and object-oriented programming principles.

If you're comfortable with these topics, you’re ready to proceed!

What Is an ArrayList?

An ArrayList is a dynamic array. Unlike a traditional array with a fixed size, an ArrayList can grow or shrink as needed. This flexibility makes it an essential tool in many applications. Key features of an ArrayList include:

• Dynamic resizing: Automatically increases capacity when needed.

• Element manipulation: Easy addition, removal, and access of elements.

• Random access: Elements can be accessed using an index.

We’ll implement these features in our custom ArrayList.

Step 1: Define the Structure

To get started, we’ll create a generic class called MyArrayList. It will include:

1. An internal array to store elements.

2. A size variable to keep track of the number of elements.

3. A default capacity for the initial size of the array.

Here’s the code:

class MyArrayList<E> {
    private int DEFAULT_CAPACITY = 10;
    private int size = 0;
    private E[] arr;

    public MyArrayList() {
        arr = (E[]) new Object[DEFAULT_CAPACITY];
    }
}

This creates the foundation of our ArrayList.

Step 2: Implement Core Methods

Now, let’s add the essential functionality.

Adding Elements

We’ll start with a method to add elements to the ArrayList. When the array is full, we’ll resize it to accommodate more elements.

    public void add(E e) {
        if (size == arr.length) {
            increase();
        }
        arr[size++] = e;
    }

    private void increase() {
        int newSize = arr.length * 2;
        arr = Arrays.copyOf(arr, newSize);
    }

The ensureCapacity method doubles the array size when needed, and the add method appends a new element.

Accessing Elements

To retrieve elements, we’ll implement a get method that includes bounds checking to avoid accessing invalid indices.

    public E get(int i) {
        if (i>=size || i<0) {
            throw new IndexOutOfBoundsException("Index: " + i + ", Size " + size);
        }
        return (E) arr[i];
    }

Removing Elements

The remove method deletes an element by shifting all subsequent elements to the left.

    public E remove(int i) {
        if (i>=size || i<0) {
            throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + size);
        }
        E removedElement = (E) arr[i];
        for (int j=i; j<size-1; j++) {
            arr[j] = arr[j+1];
        }
        arr[--size] = null; // Prevent memory leaks
        return removedElement;
    }

Step 3: Add Utility Methods

To make our ArrayList easier to use, we’ll add some helper methods:

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        arr = (E[]) new Object[DEFAULT_CAPACITY];
    }

These methods provide basic information about the list and allow users to reset it.

Step 4: Testing the Custom ArrayList

Let’s write a main method to test our MyArrayList:

class Tests {
    public void runTests() {
        testAdd();
        testDelete();
    }

    private void testAdd() {
        MyArrayList<Integer> le = new MyArrayList<Integer>();
        le.add(10);
        int result = le.get(0);
        if (result == 10) {
            System.out.println("testAdd passed.");
        } else {
            System.out.println("testAdd failed. Expected 10 but got " + result);
        }
    }

    private void testDelete() {
        MyArrayList<Integer> le = new MyArrayList<Integer>();
        le.add(10);
        le.add(20);
        le.remove(0);
        int result = le.get(0);
        if (result == 20) {
            System.out.println("testDelete passed.");
        } else {
            System.out.println("testDelete failed. Expected 20 but got " + result);
        }
    }
}

With this simple test, you can verify the core functionality of your custom ArrayList.

Step 5: Driver Code

Lastly our driver code to run the tests

    // Driver method 
    public static void main(String[] args) {
        MyArrayList<Integer> le = new MyArrayList<Integer>();
        le.add(10);
        le.add(20);
        System.out.println(le.get(0));

        Tests tests = new Tests();
        tests.runTests();
    }

---

Step 6: Comparing with Java’s Built-In ArrayList

Our implementation provides basic functionality similar to Java’s ArrayList. However, the built-in ArrayList includes advanced features like:

• Iterators for traversing elements.

• Thread-safety options (with Collections.synchronizedList).

• Better error handling and performance optimizations.

While our version is more limited, understanding its inner workings lays the groundwork for deeper insights into Java’s standard library.

Conclusion

In this blog post, we implemented a simple version of an ArrayList in Java, covering dynamic resizing, adding, removing, and accessing elements. This exercise is an excellent way to strengthen your understanding of data structures and Java programming.

Ready to take it further? Try adding features like iterators, sublists, or synchronization to enhance your custom ArrayList. The possibilities are endless!

If you'd like to explore the complete code, check out the GitHub repository. Happy coding!