Creating an Araylist

Overview

Today we will look at creating our own implementation of Java's Arraylist. We'll do this for a few reasons:

You will see that an Arraylist is just a slightly more convenient version of an array, and uses an array to actually store the data.
We will see the algorithms that go into the convenient methods the Arraylist provides, such as automatically expanding the array, inserting into the middle, and removing elements.
It is good to understand how the things you use are really working.

Basic Outline

We will begin by making a class called "DynamicList". We won't call it Arraylist so that we can be sure we are not actually using the real Arraylist that comes with Java.

For now, we will restrict it to only store String objects. In the next lesson we will see how to make it work with any type of data. So for its private data, we will keep an array of String objects, and an integer for the current size of the list.

We also provide two constructors. The first uses a default size of 10, while the second allows the user to pass in the size. Both of these refer to the initial capacity of the list. Either way, the list starts empty.


public class DynamicList {
    private String [] array;
    private int size;

    public DynamicList() {
        array = new String[10];
        size = 0;
    }

    public DynamicList(int capacity) {
        array = new String[capacity];
        size = 0;
    }

Next, we can write a simple add method which takes a new String. The method will stick this into the next available slot, and increment the size field:


    public void add(String item) {
        array[size] = item;
        size++;
    }

Now let's add the "get" method which is used to retrieve data out of the list, at a specific index. First we must check that the index is within the bounds allowed. Here we use the current size (how many things we've added) and not the upper capacity. If the index is out of bounds, we throw the appropriate exception.

If we make it pass the exception, we can safely just pull the item out of the array at the requested index.


    public String get(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size) {
           throw new IndexOutOfBoundsException();
        } 

        return array[index];
    }

We will also add a method to return the size of the list:


    public int size() {
        return size;
    }

And a method to clear the list, which can be as simple as setting the size back to zero:


    public void clear() {
        size = 0;
    }

Resizing the Array

The code above is a good first attempt, but it has a major flaw. The problem is that if we call the add method enough, we will fill up the array we created in the constructor and overflow the bounds of the array, crashing the program.

To fix this, we should check if the array is full before adding new items, and expand the array in those cases:

 
    public void add(String item) {
        if (size == array.length) {
            resize();
        }

        array[size] = item;
        size++;
    }

To actually expand the array, we can follow the following algorithm:

Make a new, larger, array
Copy the items from the old array into the new one
Change the reference to our array to point to the new array instead

It's up to us how much bigger to make the array. If we make it just a little bit bigger, we will have to expand more often but waste less space. If we make it way bigger, we will rarely have to expand, but have more unused memory. Here we double the size:


    private void resize() {
        String [] temp = new String[size * 2];
        for (int i = 0; i < size; i++) {
            temp[i] = array[i];
        }
        array = temp;
    }

With these additions, the DynamicList is starting to take shape! We can use it instead of an array and not have to worry about running out of room. Now we will turn to adding some of the niceties that the Arraylist gives us.

Adding Anywhere

We will start by adding the version of the add method that allows us to specify an index at which to add the new elements. We again start by resizing the array if needed.

Next we need to shift elements to the right to make space for the new item to be inserted. We do this by looping from the end of the array left, until we get to the slot we want to insert into. Each time, we move the item one cell forward. This makes a gap for the new item, which we then insert.


    public void add(int index, String item) {
       if (size == array.length) {
           resize();
       } 
       
       for (int i = size-1; i >= index; i--) {
            array[i + 1] = array[i];
       }

        array[index] = item;
        size++;
    }

Removing Items

Removing an item from an array means overwriting it with something else. So to implement the remove method, we will shift all the items to the right of the item we wish to remove left one cell, so that it is overwritten.

We again do this with a for loop, shifting one item at a time:


    public void remove(int index) {
        for (int i = index + 1; i < size; i++) {
            array[i - 1] = array[i];
        }

        size--; 
    }

Searching

The last convenience we will include is a search method. We do this using the linear search algorithm where we simply begin at the start of the list and check each item to see if it's the one we want. It's important that we use .equals instead of == here!


    public int indexOf(String target) {
        for (int i = 0; i < size; i++) {
            if (array[i].equals(target)) {
                return i;
            }
        }

        return -1;
    }

This also makes it easy to add in a method that removes an item from the DynamicList by value instead of by index. We implement this by first searching for the item given. Then, if it's found we ask our other remove method to remove the item at the index it was found at:


    public void remove(String item) {
        int index = indexOf(item);
        if (index != -1) {
            remove(index);
        }
    }

All of this is a good start on the DynamicList. Next time we will focus on fixing the issue of only being able to store String objects!