Data Structures

A way of organizing data that enables efficient storage, retrieval, and use.

Arrays

This is a data structure that stores elements of the same type (generally). It's important to note that you'll often see arrays referred to as in documentation, but the variable names you use when coding should be descriptive and begin with lowercase letters.

You can think of an array, , of size as a contiguous block of cells sequentially indexed from to which serve as containers for elements of the array's declared data type. The length, , of the array is fixed, meaning it cannot be resized without creating a new array. To store an element, , in some index of array , use the syntax A[i] and treat it as you would any other variable (i.e., A[i] = value;). An element of an array can be accessed in constant time. For example, the following code:

Example (Java)

// the number of elements we want to hold
final int _arraySize = 4; 

// our array declaration
String[] stringArray = new String[_arraySize]; 

for(int i = 0; i < _arraySize; i++) {
    // assign value to index i
    stringArray[i] = "This is stored in index " + i; 
    
    // print value saved in index i
    System.out.println(stringArray[i]); 
}

saves and then prints the values listed below in their respective indices of :

This is stored in index 0
This is stored in index 1
This is stored in index 2
This is stored in index 3

Most languages also have a method, attribute, or member that allows you to retrieve the size of an array. In Java, arrays have a attribute; in other words, you can get the length of some array, arrayName, by using the arrayName.length syntax.

Note: The final keyword used in the code above is a means of protecting the variable's value by locking it to its initialized value. Any attempt to reassign (overwrite) the value of a final variable will generate an error.

A Note on Arrays in C++

If you want to create an array whose size is unknown at compile time (i.e., being read as input), you need to create a pointer to whatever data type you'll be declaring your array as (e.g., char, int, double, etc.). Then you must use the new operator to set aside the space you need for your array. The example below shows how to create an array of type DataType and unknown size n that is read from stdin.

Example (C++)

// array size
int n; 
cin >> n;

// create array of unknown size n
DataType* arrayName = new DataType[n]; 

Additional Language Resources

C++ Arrays

Practice

Try out this simple challenge to verify your understanding of arrays.

Fundamental Concept

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 range because 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.