Array (ADT)

The array is a basic abstract data type that holds an ordered collection of items accessible by an integer index. These items can be anything from primitive types such as integers to more complex types like instances of classes. Since it's an ADT, it doesn't specify an implementation, but is almost always implemented by an array (data structure) or dynamic array.

Unless otherwise specified, for the remainder of this wiki the word "array" will refer to the abstract data type and not the data structure.

Arrays have one property: they store and retrieve items using an integer index. An item is stored in a given index and can be retrieved at a later time by specifying the same index. The way these indices work is specific to the implementation, but you can usually just think of them as the slot number in the array that the value occupies. Take a look at the image below:

Array ^[1]

In this visual representation of an array, you can see that it has a size of six. Once six values have been added, no more can be added until the array is resized or something is taken out. You can also see that each "slot" in the array has an associated number. By using these numbers, the programmer can directly index into the array to get specific values. Note that this image uses one-based numbering. Most languages use zero-based numbering where the first index in an array is 0, not 1.

Python's list built-in provides array functionality. C, C++, C#, Java, and a few other languages all have similar syntax for working with arrays. Here's how you would initialize an array in Java and then assign a value to an index. The following code creates a new array with size 5 and sets index 2 equal to 4.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/* Static Allocation (will be allocated in the stack)*/
int arr[5];
arr[3] = 5;

/* Dynamic Allocation  (will be allocated in the heap)*/
int *arr = new int[5];
arr[3] = 5;

/* ... */
/* Remember to de-allocate memory allocated in the heap when you're done.*/
delete [] arr;

1
2

int[] newList = new int[5];
newList[2] = 4;

You can think about arrays as a group of numbered boxes that only hold one item each. Say we have 10 boxes. That means we can't store 11 items because that's more than the number of boxes we have. If I want to store my phone in box number 5, I can go directly there and place it in the box. Later, if I want to see what's in box number 5, I can again go directly there to look inside and see my phone.

Arrays have vastly different functionality across various implementations, but the following operations can be found in all cases. They form the basis for other, more complicated operations.

Function Name*$\hspace{10mm}$	Provided Functionality
set(i, v)	Sets the value of index i to v
get(i)	Returns the value of index i

Exact names are not required. In fact, some functionality may be provided by a given language directly via special syntax.

Using these basic functions, you can engineer more complicated and useful ones. Let's see if we can figure out how to make some more complicated functions.

1) How would you print out every element in an array? (Note: This is sometimes called traversal.)

We know the size of our static array. Let's say it's 10. Then, we simply run our get(i) function for every index from 1 to 10.

2) How would you determine if a certain value is in an array? (Note: This is sometimes called search.)

This is very similar to question #1. If we know our size is 10, we can get(i) for every index. If, at any time, we get back the value we're looking for, we know the array contains our value.

3) How would you add two arrays together? (Hint: You have to create a new array.)

Let's say we have two arrays, A and B. A has size 4 and B has size 6. If we want to do the operation A + B, we need to create an array C with size 10. Then, we can search through every element in A and add them to the corresponding index in C. Then, we'll look through every element in B and add them to the corresponding index plus 4 in C. It would look something like this:

1 2 3 4 5

>>> A = [0,2,4,6] >>> B = [1,3,5,7,9,11] >>> C = A + B >>> C [0,2,4,6,1,3,5,7,9,11]

The Java array type is an example of an implementation of the array abstract data type that uses an array data structure. Other implementations exist in other languages that we'll look at later.

Creating an array:

Arrays require a size and type when they are created in Java. Below is an example of how you would declare an array of integers with size 10.

Creating an array

1 2 3

>>> int[] myArray = new int[10]; >>> System.out.print(Arrays.toString(myArray)); [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Notice how the array defaults to using zeros. This is because we created an array of integers. If we created an array of strings, the default value would be null.

1 2 3

>>> String[] myArray = new String[10]; >>> System.out.print(Arrays.toString(myArray)); [null, null, null, null, null, null, null, null, null, null]

Setting values:

To set a value at a certain index into the Java array, you use the [] syntax. The index goes inside the brackets, and the value goes on the other side of the equation. In Java, indexes start at zero! Remember to do the appropriate research for your programming language to know how it handles indexes.

1
2
3
4
5

>>> int[] myArray = new int[5];
>>> myArray[1] = 100;
>>> myArray[3] = 200;
>>> System.out.print(Arrays.toString(myArray));
[0, 100, 0, 200, 0]

Getting a value:

Getting a value at a certain index uses the same notation as setting a value.

Getting an index's value

1 2 3 4

>>> int[] myArray = new int[5]; >>> myArray[1] = 100; >>> System.out.print(myArray[1]); 100

In Java, you can create an array of any primitive data type, abstract data type, or custom class. Java also provides an ArrayList type which gives you more flexibility.

Let's look at arrays in other languages. All of the languages below have the same strict implementation of array as Java. In each, we'll create an array of integers, sum its elements, and print it.

Python:

1 2 3 4 5 6 7 8 9

def sum_elements(): my_array = [None,] * 3 # declaring and using a list in this way isn't Pythonic my_array[0] = 1 # instead you'd make an empty list and use the append method my_array[1] = 3 # but if we did that here, then we wouldn't be showing off its my_array[2] = 5 # array functionality very much sum = 0 for i in range(0, len(my_array)): sum += my_array[i] print(sum)

Java:

1 2 3 4 5 6 7 8 9 10 11

public void sum_elements(){ int[] myArray = new int[3]; myArray[0] = 1; myArray[1] = 3; myArray[2] = 5; int sum = 0; for (int i = 0; i < myArray.length; i++) { sum += myArray[i]; } System.out.print(sum); }

C++:

1 2 3 4 5 6 7 8 9 10 11 12

void sum_elements() { int len = 3; int myArray[len]; myArray[0] = 1; myArray[1] = 3; myArray[2] = 5; int sum = 0; for (int i = 0; i < len; i++) { sum += myArray[i]; } std::cout << sum; }

In C++, we have to know the size of the array to construct our for loop.

Many computer games like board games or FPS games make use of a two-dimensional "board" or matrix. Programs that deal with such problems need a way of representing objects in a two-dimensional space. A natural way to do this is to use a two-dimensional array, where we use two indices say $i$ and $j$, to refer to the cells in the array. The first index usually refers to a row while the second index refers to a column number. Using such arrays, we can easily represent any problems requiring two-dimensional data structures.

Write a program that sums two square matrices.

Example solution in Java

1 2 3 4 5 6 7 8 9 10

//A and B are the two matrices being added together public static int[][] sum_matrices(int[][] A, int[][] B) { int[][] C = new int[A.length][A[0].length]; for (int i = 0; i < A.length; i++) { for (int j = 0; j < A[0].length; j++) { C[i][j] = A[i][j] + B[i][j]; } } return C; }

The idea of multi-dimensional arrays can also be extended to three-dimensional situations where we might use an array of array of arrays. It can, in fact, be extended to any number of dimensions.

1. Doe, J. UC Davis ECE Prelim Wiki. Retrieved April 10, 2016, from http://1.bp.blogspot.com/_kLg3mPfGL6E/S_nN7gNjwHI/AAAAAAAAALA/v3AcbLZ-kAc/s1600/one+dimension+array.jpg