ArrayList
pic source: Google
While an array has a fixed size (meaning you can't add more
elements to the end once it's full), an ArrayList (sometimes
called a resizable or dynamic array) will grow as needed. If you need to add,
or additional elements, an ArrayList expands to accommodate this.
We use an ArrayList
when we want the benefits of an array (constant-time access to elements at particular
indices) but don't know up front how many elements we'll need to store.
Additionally, different languages handle arrays and ArrayLists in different
ways.
In Java, we use
both arrays and ArrayLists (depending on our needs):
//An array of Person objects
Person[] peopleArray = new Person[numberOfPeople];
// An ArrayList of Person objects
ArrayList<Person> peopleArrayList = new ArrayList<Person>();
In Python, there isn't really a true array but rather we
use lists that
are essentially an implementation of an ArrayList. We use the following syntax
to declare lists in Python:
# An empty list
peopleArrayList = []
# A list with elements
myList = [1, 2, 3]
Python also has an array module,
but the only real difference between this and a list is that an array restricts
the type of values the array can hold to some type specified when the array was
created.
For example:
import array
# Create an array of integers and initialize it with the
list [1, 2, 3]
myArray = array.array('i', [1, 2, 3])
# Print each element of the array
for i in myArray:
print(i)
# Append an integer to the end of the array
myArray.append(4)
print(myArray)
The code above produces this output:
1
2
3
array('i', [1, 2, 3, 4])
Just like with Python lists, we were able to use the append method
to add an element to the end of the array (effectively increasing its size);
however, if we were to try something like myArray[5] = 5, we would get IndexError:
array assignment index out of rangebecause the index is larger than the array's
current length.
How Do They Work?
Consider an ArrayList, , with capacity . Once 's
underlying array is filled to capacity with values, a new underlying
array is created that has increased capacity. The elements currently
stored in are then copied over to the new, larger capacity array,
and the new array replaces 's original underlying array.
Typically, the
increased capacity is some manner of rough doubling though the actual amount
that the capacity increases depends on the implementation of ArrayList you're
using. In some Java implementations, the ensureCapacity method in ArrayList class
uses this to determine the new size of the underlying array:
int newCapacity = (oldCapacity * 3)/2 + 1;
Increasing the capacity by what amounts to is
still enough to give some guarantees: access and insertion
(on average). This has the advantage of wasting slightly less space when the
ArrayList is not very full.
What About Performance?
An ArrayList hits capacity (i.e., has to copy the contents
of its underlying array over to a new array of double size) infrequently enough
that storing values in an ArrayList still averages out to constant time (as
opposed to linear time).
Example
The Java code below provides an ArrayList implementation:
import java.util.*;
public class ResizableArray<E> {
/** Default
initial capacity of underlying array **/
final private int
_initialCapacity = 10;
/** Underlying
array **/
private Object[] items;
/** Current
number of elements **/
private int size;
/** Create a
ResizableArray with a default initial capacity. **/
public ResizableArray()
{
this.items = new
Object[_initialCapacity];
this.size = 0;
}
/** Create a
ResizableArray with a specific initial capacity.
@param
capacity The initial capacity for the underlying array.
**/
public ResizableArray(int
capacity) {
this.items = new
Object[capacity];
this.size = 0;
}
/** Add an
element to the end of the array (will automatically resize if current capacity
is reached). **/
public void append(E
element) {
ensureExtraCapacity();
items[size] =
element;
size++;
}
/** Check if the
array has enough capacity to append a value; if the array is full, doubles the
underlying array. **/
public void ensureExtraCapacity()
{
if(size == items.length)
{
Object[] copy
= new Object[size << 1];
System.arraycopy(items,
0, copy, 0, size);
items = copy;
}
}
/** @param index
An index for an element currently stored in the ResizableArray.
@return The
element located at index.
**/
public Object get(int
index) {
checkBounds(index);
return items[index];
}
/** Overwrite the
value at some index.
@param index
The index to be set.
@param value
The value to be set.
**/
public void set(int
index, E value) {
checkBounds(index);
items[index] =
value;
}
/** Check if
insertion index is valid.
@throws
ArrayIndexOutOfBoundsException if index is negative or larger than the current
size.
**/
public void checkBounds(int
index) {
if(index <
0 || index >= size) {
throw new
ArrayIndexOutOfBoundsException(index);
}
}
/** Print the
contents of the array. **/
public void print()
{
System.out.print("[");
if(size > 0)
{
for(int i
= 0; i < size - 1; i++) {
System.out.print(items[i]
+ ", ");
}
System.out.print(items[size
- 1]);
}
System.out.println("]");
}
/** Print the
contents of the array.
@param name
The array name to precede the array contents.
**/
public void print(String
name) {
System.out.print(name
+ ": ");
print();
}
}
Now, consider the following main method:
public static void main(String[] args) {
ResizableArray<Integer>
arrayListInt = new ResizableArray<Integer>();
ResizableArray<String>
arrayListString = new ResizableArray<String>(20);
arrayListInt.print("arrayListInt");
System.out.println("arrayListInt
current size: " + arrayListInt.size);
System.out.println("arrayListInt
current capacity: " + arrayListInt.items.length);
for(int i = 0; i <
12; i++) {
arrayListInt.append(i);
}
arrayListInt.print("arrayListInt");
System.out.println("arrayListInt
new capacity: " + arrayListInt.items.length);
System.out.println("arrayListInt
new size: " + arrayListInt.size + "\n");
arrayListString.print("arrayListString");
arrayListString.append("Hi");
arrayListString.print("arrayListString");
arrayListString.set(0,
"Bye");
arrayListString.print("arrayListString");
}
When run, it produces this output:
arrayListInt: []
arrayListInt current size: 0
arrayListInt current capacity: 10
arrayListInt: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
arrayListInt new capacity: 20
arrayListInt new size: 12
arrayListString: []
arrayListString: [Hi]
arrayListString: [Bye]
Observe the following:
ArrayListInt was created using the default
constructor, so it has an initial capacity of ; however, we were able to
add elements to it using the append method because ensureExtraCapacity resized
our underlying array and copied everything over.
The set method overwrote the contents of the
first element (i.e., index ) of arrayListString.
