An ArrayList in computer programming is a data structure that behaves like a computer array but also implements the ability to dynamically grow the size of the array as needed. Unlike an intrinsic array data type, which cannot be resized during program execution, the ArrayList structure can grow and shrink the size of the array in response to the addition or deletion of elements. It has a very favorable performance profile, allowing fast random access to the data collection. There are two instances, however, in which it is slower than some other data structures, namely the addition and removal of elements from the middle of the array. Most object-oriented programming languages have some type of implementation of such a list, although they are sometimes called dynamic arrays.
Using an ArrayList provides a program with the ability to access data objects with an index number instantly instead of having to walk through an entire sequence of data to find an address, which is required with linked lists. With the ability to increase the size of the array as needed, it is a very balanced approach that considers both flexibility and speed. Additionally, when elements are removed from such a list, the size of the array is reduced, freeing up memory space.
One benefit of using an ArrayList over some other data structures is that a wrapper object is not required to contain the data being stored. In the case of a linked list or a hash table, a separate object is usually needed to maintain the technique being used to hold and manipulate the collection. With an ArrayList, the only information needed about the data objects is the address of the object in memory. This means there will be less overhead memory usage when working with this type of list.
A potential problem with using an ArrayList can come from the implementation and memory management system. Most arrays are allocated as consecutive memory locations. So, to use an ArrayList of a certain size, at least that much memory must be available in an uninterrupted sequence of blocks. The dynamic array could resize itself several times, so memory fragmentation can occur and lead to a memory allocation failure, halting program execution.
The performance of an ArrayList is similar to that of using a standard array, although access times are slightly slower because the array is encapsulated in an object. One instance in which a dynamic array can slow down dramatically, depending on implementation, is when the size of the array needs to be changed. This can involve copying the current array into a new array that was allocated to the new desired size, causing a temporary degradation in performance. The same problem can be experienced when adding or removing an element from the middle of the list, causing all following elements to have to be moved to a new location.
