An Array List in Java

An array list, also called a dynamic array, is a variable-sized data structure to which elements can be added and removed. Like a linked list, it can serve as the underlying data structure behind a stack or a queue.

The simplest way to build a dynamic array is to store the data in a traditional array, which is copied to a new, larger array when it gets full. This means that most insertions are O(1), but that inserting when the underlying array is full becomes an O(N) operation. A real implementation might also de-allocate some of the memory if we remove elements below a certain threshold.

ArrayList

Here’s the code for an array list which allows insertions only at the end and expands by a factor of 2 when it gets full:

Some code to demonstrate the functionality:

And the output: