Arrays: Lesson

An *array* is a grouping of variables of the same type into contiguous blocks of memory. This data structure is especially useful in applications when there are many variables of the same type that are related to each other. Consider the example of having to store the three coordinates of a point in space (coordinates x, y, and z). A valid way you can store these coordinates in variables is:
```cpp
int main() {
  int xCoordinate = 1;
  int yCoordinate = 2;
  int zCoordinate = 3;
}
```
While this is okay, especially for a small number of coordinates, it will become harder to manage as the number of coordinates increases. A solution to this problem is to store the coordinates in a data structure called an *array* like so:

```cpp
int main() {
  int coordinates[3] = {1, 2, 3};
}
```

This piece of code declares a variable of type `array` called `coordinates`. Since the three coordinates are related to each other and are likely to be used together frequently, the `coordinates` array neatly stores them into one variable. We will explore how to access and manipulate the elements of an array in future exercises. Under the hood, the `coordinates` variable creates three `int` variables in memory which are stored contiguously. As a visual representation, you may think of arrays as a group of lockers, not unlike those found in a gym, where each locker is responsible for storing one variable of type `int` (or any other variable type you have learned about so far).


Introduction to Arrays

The main benefit of arrays is the ability to work with large amounts of data without assigning each piece of data its own variable name; therefore arrays usually contain many elements. To work with these elements, you will probably have to do something repeatedly. As you learned earlier in the course, a loop is used in order to execute repeated code. The technique of using a loop on an array is called “looping through the array.” Recall the two kinds of loops: a `for` loop and a `while` loop.

Let’s first take a look at how to loop through an array using a `while` loop. Consider the example of having an array consisting of 20 random integers and you wish to print its contents to the screen. Here’s how this is done with a `while` loop: 

```cpp
#include<stdio.h>

int main() {
  int arr[] = {6, 9, 18, 37, 4, 23, 27, 16, 1, 30, 22, 7, 10, 25, 3, 2, 35, 11, 19, 28}; // Array
  int i = 0; // Initialize index i to zero
  while(i < 20){ // while loop
    printf("%i\n", arr[i]); // Access element at index i in arr and print 
    i++; // Increment the index
  }
}
```
In this piece of code, we have the 20 integer array `arr`. An index variable is declared and initialized outside of the loop. The loop runs for indices less than the size of the array (in this case, it is 20). The element at index `i` is printed along with a new line. Finally, the index is incremented by one.

This same process can be done using a `for` loop like so:

```cpp
#include<stdio.h>

int main() {
  int arr[] = {6, 9, 18, 37, 4, 23, 27, 16, 1, 30, 22, 7, 10, 25, 3, 2, 35, 11, 19, 28}; // Array
  for(int i = 0; i < 20; i++){ // for loop
    printf("%i\n", arr[i]); // Access element at index i in arr and print
  }
}
```


Looping Through Arrays

Good Job! You have just completed the lesson on arrays, probably the most used data structure in software development. Here is a quick recap of everything:

* Arrays are a special data type that allows you to group together many variables that are related. An array of 100 elements saves you the trouble of having to create 100 variables in your code.

* Arrays can be of any data type, be it primitive, custom-made, or even other arrays.

* Arrays are immutable, so the number of elements must be known at creation time in order for the program to know how much memory to reserve.

* After creation, elements may not be added or deleted from the array.

* Upon creation, an array can be initialized or uninitialized.

* A single dimension uninitialized array is created like this:

  * > `data_type name[array_size];`

* A single dimension initialized array is created like this:

  * > `data_type` name[] = {`first_value’, ‘second_value’, ‘third_value’, …};

* In the initialized case, the size of the array is inferred from the number of elements that are supplied.

* All elements of an array occupy contiguous locations in memory. 

* An element in an array can be accessed like so:

  * > `arr[idx]`

* The first element in an array is always at index 0, the last element is at index `array_length - 1`, the *n*th element is at index `n-1`.

* Elements in an array can be modified like this:

  * > `arr[idx] = new_value`

* Since arrays usually contain many elements, the most efficient way to work with them is by using a loop (`for` loop or `while` loop).

* Multidimensional arrays are simply arrays of arrays. They are created, accessed, and modified in the same way as their single dimension counterpart.

At this point, you should be comfortable working with arrays when you need to. Use them wisely!


Review

As we said before, arrays can contain any kind of data type, be it `int`, `char`, or anything else. Interestingly, arrays can also store other arrays! An array containing other arrays is known as a *multidimensional array*. These kinds of arrays are frequently used in mathematical applications that involve matrices and vectors. Similar to its single dimension counterpart, a multidimensional array can be initialized or uninitialized upon its creation. Let’s take a look at the uninitialized version first. The following is a two-dimensional array of integers called `mat` which represents a three-by-four matrix:

```cpp
int mat[3][4];
```

The previous code indicates that the array `mat` contains three elements each of which is an array that contains four integers. To visualize this, consider a row of three lockers, in which each locker contains four sub-lockers that someone can store items in. To illustrate how to create an initialized multidimensional array, we will create a two-by-three multidimensional array called `mat2` composed of random integer values.

```cpp
int mat2[][3] = {{1, 6, 3}, {5, 9, 2}};
```

Just like in the single dimension case, the array is initialized by placing elements between `{}` brackets. In this case, the elements inside the outermost brackets are arrays of three elements each. It is important to note that while the two-by-three dimension can be inferred from the right-hand side of the expression, the only dimension that can be omitted is the first (notice the first `[]` is empty); all others must be supplied. The array `mat2`, represents this table:

![2x3 matrix example](https://static-assets.codecademy.com/Courses/learn-c/arrays-and-strings/Two-by-Three-Matrix.svg)

While it is possible to have a theoretically infinite number of dimensions, in practice, dimensions greater than two are very rare. For a two-dimensional matrix, the first dimension represents the number of rows and the second dimension represents the number of columns.


Multidimensional Arrays

Array elements can be accessed, modified, and used just like any other variable of the same data type. The following shows how to access an element in an array at index `idx`:

> `arr[idx]`

The first element in an array has index 0 and the last element in an array has index `arraySize - 1`. The *n*th element is at index *n-1*, so, for example, the third element would be at index 2.

An element in an array is modified just like a regular variable:

> `arr[idx] = newValue`

Remember to be consistent with the data types! For example, elements of an array of integers can only be modified to represent other integer values; anything else will cause errors. When working with arrays, it is important to be careful and not attempt to access an element at an index greater than `arraySize - 1` as the memory located there could be storing other data. Accessing an array at an index greater than `arraySize - 1` will return a random value. Modifying an element at an index greater than `arraySize - 1` will corrupt the data stored at that location, causing the program to behave in an unpredictable manner. The same is true for array access at indices less than zero.

The following piece of code changes an element in an array and assigns it to a lone variable:

```cpp
#include<stdio.h>

int main() {
    int arr[] = {3, 5, 7, 9}; // Array creation
    arr[2] = 6; // Modify the third element
    int x = arr[2]; // Assign the third element to the lone variable x
    printf("%i", x); // Print x
}
```

Array Access and Element Modification

An array is a collection of data that can be of any type. For example, you can construct an array of `int`s, `bool`s, `char`s, etc. 

There are two types of arrays that can be created: an initialized array or an uninitialized array. As its name implies, an uninitialized array is created without specifying the initial values it contains. As an example, we will create an uninitialized array called `age`, containing four variables of type `int`, which represents the age of four siblings:

```cpp
int age[4];
```
To indicate to the compiler that `age` is an array of `int`s and not a single `int` variable, we append `[arraySize]` (in this case, `arraySize` is four) to the end of the variable name.

The general template for creating an uninitialized array is:

> dataType name[arraySize];

When you create an uninitialized array, you are required to specify its size so that the compiler may reserve the proper amount of memory blocks.  Once it is created, the size of the array cannot be changed; this means that arrays are *static*. An uninitialized array can be populated later in a program.

In contrast, an initialized array is created by specifying the initial value of its elements. As an example, we will create an `age` array with four initial ages:

```cpp
int age[] = {7, 27, 34, 63};
```

The general template for creating an initialized array is:

> dataType name[] = {firstValue, secondValue, thirdValue, …};

Notice that in this case, you don't need to specify the size of the array as it is implied from the number of elements supplied; however, declaring an initialized array with the size specified will also work. The previous example could have also been written like this:

```cpp
int age[4] = {7, 27, 34, 63};
```

Creating and Initializing Arrays

Elements in a multidimensional array are accessed in like so:

> array[rowNumber - 1][columnNumber - 1];

Similar to their single dimension counterparts, the first row is at index 0, the *n*th row is at index n-1, and the last row is at index `firstDim - 1`. This is the same for the columns too.

Consider this example of a three-by-three matrix of integers:

```cpp
int mat[][3] = {{19, 6, 7}, {20, 3, 17}, {16, 13, 10}};
```

To access the element on the second row and third column, we write `mat[1][2]` (in this case it's 17).

Looping through a multidimensional array is similar to looping through a single dimension array with the slight difference that having multiple dimensions will require nested loops. While you can use nested `while` loops, it is better to use a nested `for` loop. In the two-dimensional case, the outer loop goes through the rows and the inner loop goes through the columns:

```cpp
int mat[3][3] = {{12, 8, 2}, {17, 19, 5}, {6, 11, 2}};

for(int i = 0; i < 3; i++){
  for(int j = 0; j < 3; j++){
    int num = mat[i][j];
    printf("%i\n", num);
  }
}
```

To prevent the hardcoding of dimensions in a loop, the `sizeof()` function is used as follows:
* rowDimension = sizeof(matrix)/sizeof(matrix[0]);
* columnDimension = sizeof(matrix[0])/sizeof(dataType);

Let's use these identities to write the `for` loop from the previous exercise:

```cpp
int mat[3][3] = {{12, 8, 2}, {17, 19, 5}, {6, 11, 2}};

int rowDimension = sizeof(mat)/sizeof(mat[0]);
int columnDimension = sizeof(mat[0])/sizeof(int);

for(int i = 0; i < rowDimension; i++){
  for(int j = 0; j < columnDimension; j++){
    int num = mat[i][j];
    printf("%i\n", num);
  }
}
```


Element Access in Multidimensional Arrays

Up to now, when looping through an array, the size of the array has been hardcoded into the loop condition. This is bad practice as it makes the loop only applicable to arrays of a single size. To make a loop valid for arrays of any size, the `sizeof()` function is used. `sizeof()` is a special function that returns an integer that is the size of the array in bytes. The syntax for this function is as follows:

> `sizeof(arr);`

Here is an example:

```cpp
int main() {
  int arr[] = {3, 8, 4, 0, 9}; 
  int len = sizeof(arr); // Assign size of array to variable len
  printf("%i", len);
}
```

The array has five elements in it, however, this code will output the number 20 as opposed to five because `sizeof()` returns the total number of bytes occupied by the array regardless of the type of elements. Recall that a variable occupies several bytes in memory determined by its type. In this case, the array has five integers each of which occupies four bytes of memory; therefore the total size is *5 x 4 = 20* bytes. To get the actual number of elements in the array, we have to divide the total size of the array by the size of the data type it contains. Fortunately, the `sizeof()` function can also be applied to any data type to determine its size in memory. The syntax is the same as that for an array:

> sizeof(dataType);

We can modify the variable `len` to represent the number of elements in the array `arr` like so:

```cpp
// Assign size of array to variable len. Scale by the size of an int.
int len = sizeof(arr)/sizeof(int);
```
The code will now output the expected size of the array (five). 

Using this technique, a loop can now be written to work with arrays of arbitrary length. Here is an example:

```cpp
#include<stdio.h>

int main() {
  int arr[] = {3, 2, 10, 6, 18, 5, 8, 4, 0, 9}; 
  int len = sizeof(arr)/sizeof(int);
  for(int i = 0; i < len; i++){
    printf("%i\n", arr[i]);
  }
}
```

Notice how in the condition for the `for` loop, the variable `len` is used to represent the length of the array as opposed to hardcoding it in. We can further simplify the code above by eliminating the variable `len` and directly computing the size of the array in the `for` loop condition.

```cpp
#include<stdio.h>

int main() {
  int arr[] = {3, 2, 10, 6, 18, 5, 8, 4, 0, 9};
  for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
    printf("%i\n", arr[i]);
  }
}
```