ArrayLists: An Introduction to the What, Why, Where, and How

Written By:

Nestor Rubio

Last Updated:

December 5th, 2023

You might have been in a lecture, a discussion, an internet rabbit hole, or in the middle of some sort of interstellar daydream when you came across the term “ArrayList”. I hope that no matter where you’re coming from, I can help clear this term up for you so that you can start understanding and implementing this powerful data structure.

Please note: If you’re not already familiar with arrays, I highly recommend gaining a solid understanding of them before diving into ArrayLists, as arrays serve as the building blocks for ArrayLists.

With that disclaimer out of the way, we can start with a simple question and work our way forward to in-depth understanding.

What is an ArrayList and Why Use It?

The concept of the ArrayList was introduced to me as the merging of typical Array behaviors with a solution to its primary drawback: the limitation on the number of items it can store.

It’s well established that once you make an Array of a certain size, you’re pretty much stuck with that amount. Wouldn’t it be nice if we could just declare an array, use it like an array, but NEVER worry about the size limit? Maybe this mysterious array could just keep expanding in size? Luckily, there is a solution and it comes in the form of the ArrayList. With the foundation of an array but the behavior of self-regulation, the ArrayList is an idea which will definitely expand the limits of your problem-solving capabilities.

The ArrayList is often defined as a class or structure (depending on the language), which typically makes use of a couple of things: an inner array, a capacity, a size, and several methods or functions defining the behavior of the ArrayList.

The inner array was a given since it needs to store the data somewhere and neither of us feels like rewriting how memory gets stored and moved around in our computer’s registers. The capacity keeps track of the temporary limit of how many items you can store in any moment. The size variable is used to keep track of how many items are currently being stored in the ArrayList. Miscellaneous methods, such as add, remove, isEmpty, clear, and others, are often optional helper functions and methods which make solving the problem at hand much easier and oftentimes makes the code much easier to read and interpret.

How to use it?

It is worth noting that not all languages require the introduction of the ArrayList data structure, many like Python use lists or a similar idea which essentially acts as what we describe the ArrayList to be and you can add to them without worry. The code samples below are written in C and Java, showing the two common implementations of ArrayLists: using the data structure straight out of the box, or creating it yourself. Both are fun but in my experience, it is always nice to build a data structure from scratch first, so you have a more in-depth understanding of some of the operations which aren’t so clear in the out-of-the-box versions.

The code used in both examples will be commented to ensure it is clear what is happening at each line.

From Scratch

  • C
  • Java
#include <stdio.h>
#include <stdlib.h>
// defining "ArrayList" to not say "struct ArrayList"
typedef struct ArrayList ArrayList;

// constant values
const int INITIAL_CAPACITY = 10;

// declaring the struct to use
struct ArrayList {
  // inner array, in this case it's integers
  int* array;
  // inner size and capacity
  int size, capacity;
};

// function to create an ArrayList
ArrayList* newArrayList() {
  // allocate the memory for the ArrayList
  ArrayList* ret = malloc(sizeof(ArrayList));

  ret->array = malloc(INITIAL_CAPACITY * sizeof(int));
  ret->capacity = INITIAL_CAPACITY;
  ret->size = 0;
  
  return ret;
}

void resize(ArrayList* list) {
  if(list == NULL) return;

  // the new capacity is calculated the same way Java's
  // ArrayList class calculates its new capacity
  int newCapacity = ((list->capacity * 3)/2 + 1);
  // reallocate memory in the inner array and expand the size of it
  list->array = realloc(list->array, newCapacity * sizeof(int));
  list->capacity = newCapacity;
}

// function to add an element to the end of an ArrayList
void add(ArrayList* list, int value) {
  if(list == NULL) return;

  // if list size is at capacity, resize it
  if(list->size == list->capacity) resize(list);

  // add the value to the end of the list, increasing size by one
  list->array[list->size] = value;
  list->size++;
}

// function to remove an element from the list
void removeAtIndex(ArrayList* list, int index) {
  if(list == NULL) return;

  // if the index is out of bounds, return
  if(index < 0 || index >= list->size) return;

  // if index is the last element, decrease size by one and return
  if(index == list->size - 1) {
    list->size -= 1;
    return;
  }
  
  // shift all elements after the index to the left by one
  // basically overriding the element at index
  for(int i = index; i < list->size - 1; i++) {
    list->array[i] = list->array[i + 1];
  }
  // decrease size by one, reflecting the removed item
  list->size -= 1;
}

// function returning -1 if null, 1 if empty and 0 if not
int isEmpty(ArrayList* list) {
  if(list == NULL) return -1;
  // if this looks weird, give ternary operators a quick search
  return list->size == 0 ? 1 : 0;
}

// function to clear the list
void clear(ArrayList* list) {
  if(list == NULL) return;

  // free the allocated memory in the array
  free(list->array);
  // reallocate the memory 
  list->array = malloc(INITIAL_CAPACITY * sizeof(int));
  list->size = 0;
  list->capacity = INITIAL_CAPACITY;
}

int itemAt(ArrayList* list, int index) {
  if(list == NULL) return -1;

  if(index < 0 || index >= list->size) return -1;

  return list->array[index];
}

int main(void) {
  ArrayList* list = newArrayList();

  // add 20 items into list (0-19), note that starting at a capacity
  // for 10 items, the capacity and size will grow accordingly
  for(int i = 0; i < 20; i++){
    add(list, i);
  }

  // remove a couple of items
  removeAtIndex(list, 0);
  removeAtIndex(list, 18);
  removeAtIndex(list,5);

  // if list is not empty (it isn't) then print the statement
  if(isEmpty(list) == 0) {
    printf("Hope ArrayLists make more sense now!\n");
  }
}
public class ArrayList {
  // defining constant values
  final private static int INITIAL_CAPACITY = 10;
  
  // defining necessary variables
  private int[] array;
  private int capacity, size;

  // constructor method
  public ArrayList() {
    this.array = new int[INITIAL_CAPACITY];
    this.capacity = INITIAL_CAPACITY;
    this.size = 0;
  }

  // getter for size & no setter because size only grows with adding an item
  public int getSize() {
    return this.size;
  }

  public int getItemAtIndex(int index) {
    if(index < 0 || index >= this.size) {
      throw new IndexOutOfBoundsException("Index out of bounds");
      // Note: errors are not necessary but could be something else to look into for extra learning if you are not familiar with them yet
    }

    return this.array[index];
  }
  /*
  No getter for capacity or the inner list because those should be abstracted away from the user. We should not let them worry about how the object works on the inside
  */
  
  // add item to arraylist
  public void add(int item) {
    // if array is full, expand array
    if (this.size == this.capacity) {
      this.expand();
    }
    // add item to array
    this.array[this.size] = item;
    // increment size
    this.size += 1;
  }
  
  // remove item at index in arraylist
  public void removeItemAtIndex(int index) {
  // if index is out of bounds, throw error
    if (index < 0 || index >= this.size) {
      throw new IndexOutOfBoundsException("Index out of bounds");
    }
    // shift all items to the left, overriding item at index
    for (int i = index; i < this.size - 1; i++) {
      this.array[i] = this.array[i + 1];
    }
    // decrement size
    this.size--;
  }
  
  // function returning whether list is empty or not
  public boolean isEmpty() {
    return this.size == 0;
    //return this.array.length == 0 could also be used but both values will be equal
  }
  
  // resize the list to allow for extra space
  // method is private because users shouldn't worry about this operation
  private void expand() {
    // declare new capacity for the list
    int newCapacity = ((this.capacity * 3)/2 + 1);

    // create new array with size of newCapacity
    int[] newArray = new int[newCapacity];
    // copy all items from old array into new array
    for(int i = 0; i < this.size; i++) {
      newArray[i] = this.array[i];
    }
    // assign array to be this new array and capacity to be new capacity
    this.array = newArray;
    this.capacity = newCapacity;
  }

  // clear list of all items
  public void clear() {
    // essentially restore to constructor state
    this.array = new int[INITIAL_CAPACITY];
    this.capacity = INITIAL_CAPACITY;
    this.size = 0;
  }
  
  // main method to test methods
  public static void main(String[] args) {
    ArrayList list = new ArrayList();

    // add 20 items into list (0-19), note that starting at a capacity
    // for 10 items, the capacity and size will grow accordingly
    for(int i = 0; i < 20; i++){
      list.add(i);
    }

    System.out.println(list.getItemAtIndex(2)); // -> 2
    System.out.println(list.getItemAtIndex(17)); // -> 17
    
    list.removeItemAtIndex(0); // removes value 0 at index 0
    System.out.println(list.getItemAtIndex(0)); // -> 1
  }
}

Out-of-the-Box

// need to import the ArrayList in order to use it
import java.util.ArrayList;

public class ArrayListOutOfTheBox {
  public static void main(String[] args) {
    // Arraylists can be of any non-primitive data type
    ArrayList<Integer> nums = new ArrayList<Integer>();
    ArrayList<String> strings = new ArrayList<String>();

    // can add freely
    nums.add(10);
    nums.add(20);
    strings.add("Hello");
    strings.add("world");

    // can get an item by index
    System.out.println(nums.get(1) + " " + strings.get(0));
    // prints "20 Hello"

    //can get sizes
    System.out.println(nums.size() + " " + strings.size());
    // prints "2 2"

    // can delete items by index
    nums.remove(0);
    strings.remove(1);

    // can get size and check if empty
    System.out.println("nums has " + nums.size() + " so is it empty? " + nums.isEmpty()); // -> "nums has 1 so is it empty? false"
    System.out.println("strings has " + nums.size() + " so is it empty? " + nums.isEmpty()); // -> "strings has 1 so is it empty? false"
    
    // clearing is easy, just reassign
    nums = new ArrayList<Integer>();
    strings = new ArrayList<String>();
  }  
}

Performance Analysis

If you have not explored the idea of algorithm analysis, I recommend reading my post about exactly that topic here. From this, you will know plenty on Big O notation and how it is being used in the analysis of ArrayList function or method performance below.

  • Get Item
    • By Indexing
      • O(1) – With the inner array being used, indexing is always constant time.
    • By Value
      • O(n) – If you are retrieving an item by a condition or by looking for a specific value, it could require looking at all elements in the list once.
  • Add Item
    • To End
      • O(1) – This is considered constant time because despite the possibility of needing to do a O(n) resize of the list, it becomes less and less likely with each expansion, meaning it can pretty much be considered constant.
    • At Specific Index
      • O(n) – Assuming you select any spot that isn’t the end of the list, all of the values to the right of the index would need to be shifted over by one index, meaning we could iterate a portion of all elements in the list.
  • Delete Item
    • O(n) – More often than not, you will be deleting an item from anywhere in the list but the end and if this is the case then the rest of the ArrayList’s values would need to be shifted to accommodate making it a linear time operation on average. If removing from end, it is O(1) since no items get moved around.
  • Size
    • Through Counting
      • O(n) – Incrementing a counter from 0 to the size of the list for each item you see is a linear time operation.
    • By Reading Integer
      • O(1) – Remember that a size integer is stored to know the size of the list at any time. Reading and returning this integer value is a constant time operation.
  • isEmpty
    • O(1) – All that really needs to be checked is the size of the list which is a constant time operation. Could also check the first index to see if an item is stored or not.

More To Learn

Possibilities

The Out-of-the-Box section showed some intro-level methods which can be used in the ArrayList class. There is a lot more that can be done with this class than I show here. If you wish to learn more about these possibilities, I strongly recommend visiting the official Oracle documentation here to see great documentation on this class and many others.

If you see a cool method you want to add to an ArrayList implementation from scratch, then give it a shot and consider it a challenge. It’ll help you grow and better understand the ArrayList as a whole.

Do I Even Have It?

As I mentioned before, not all languages need a notion of an ArrayList because they may already use Lists which are their own resizable structure, and not need to expand on the idea of an array. Whatever language you use, consider looking around and seeing whether the language needs ArrayLists to solve any issues or if there’s other ways to solve the resizable container issue.

Conclusion

We’ve explored the concept of an ArrayList from the problem it solves to how to create and use it. We’ve even seen an overview of the performance of several common methods available in an ArrayList. You now have the tools to go and solve problems where an array would be okay, but a resizable array is ideal.

I now bestow upon you the ArrayList as a data structure to add to your programming tool belt. Best of luck!

Posted

in

by

Nestor Rubio

Tags:

, , , , ,