Review of Arrays - Eishaaya/GMRDataStructuresTest GitHub Wiki

Remind me again, what is an Array?

Before introducing the linked list data structure, it is important to review the most widely used data structure in computer programming, the array. An array stores a sequence of values in memory that are of the same type. When creating an array of a particular size, you are guaranteed that the values will be contiguously placed in memory and therefore they can be accessed using an index. Typically, programming languages such as C# and Java use zero-based indexing. This means that the index of the first value is 0, and the index of the last value is N – 1, where N is the length of the array.

Due to ordered access via indexing, the array data structure is very fast. When creating an array, as shown below, the program references the first memory location and sets up a contiguous block of memory that has a size specified by the programmer. Accessing the other elements is simply a matter of starting from the first location in memory, adding a value to that memory location, and shifting the location of interest over in the sequence. The amount that is moved is specified by the index.

The downside of an array might seem obvious: what if the number of elements need to grow? For this, a new larger array must be created where the values of the old array is copied into the new array, and the new elements are added to the new array. If this is happening infrequently, the downside may be overlooked. However, if the length of the data is constantly changing in a program, arrays become an efficiency nightmare. The linked list data structure is a the solution to this problem.

An integer array of size/length 10 in C# is created as follows:

//Creates an Integer array of size/length 10
int[] randomNumbers = new int[10];

There are three steps to having a working array in C#:

• Indicate its type (int, string, double, etc)
• Give it a name
• Set its size

In the first example, the type is an int, the name is randomNumbers, and the size/length is 10. Since the values themselves are not yet initialized by the programmer, C# initializes them to 0. The new keyword is used to reserve space in memory. In this case, ten memory locations are allocated contiguously for this array.

Say you wanted to assigned random numbers between 0 and 100 to each of the values in the array above:

Random random = new Random();

int[] randomNumbers = new int[10];

for(int i = 0; i < randomNumbers.Length; i++)
{
    randomNumbers[i] = random.Next(0, 101);
}

Arrays have a property called Length that returns the size of the array. The length can be used with a for loop to run through each element of the array. In the example above, the built-in Random class and a for loop are used to initialize the array with random integers between the inclusive range of 0 and 100.

Arrays can also be initialized at compile time without specifying the size:

string[] cars = { "Tesla", "BMW", "Alpha Romeo", "Porche", "Ferrari" };

//Creates an Integer array of size with values 1, 2, 3, 4, 5 in order
int[] moreRandomNumbers = { 1, 2, 3, 4, 5 };

The size is automatically set based on the number of values entered. Although not very popular, compile-time initialization is useful when the data set is small.

---

Multidimensional arrays

---

Arrays can be multidimensional: each element of an array could reference another array, the elements of those arrays can reference other arrays, and so on. As a simple example, two dimensional arrays in C# are declared as followed:

int [,] random2dArray = new int[5, 4];

To initialize the array with random values:

//Note: The 0 notation in the random2dArray.GetLength(0) means the first dimension of the 2d array (5)
//and the 1 notation returns the second dimension (4)
for(int row = 0; row < random2dArray.GetLength(0); row++)
{
    for(int column = 0; column < random2dArray.GetLength(1); column++)
    {
        random2dArray[row, column] = random.Next(0, 101);
    }
}

Here's a visual representation of what we have created

Just like regular arrays, 2-d arrays can be initialized at compile time:

string[,] carModels = new string[,]
{
    { "Roadster", "Model S", "Model X" },  //Tesla
    { "328i", "i8", "M5" },                //BMW
    { "Spider", "GT", "Brera" }            //Alpha Romeo
};

---

Array Access Efficiency

---

Arays are instant access. To access an item inside an array is an O(1) operation.

---

Assignments to be done with arrays

---

Easy:

• Shopping list
  • An ever increasing sized shopping array where the user can always add, remove items from their list or view it.
• Login with multiple account names and passwords
  • An ever increasing sized array where the user can only login if their credentials are in the username and password array.
  • User is asked on start if they want to login or create a new account with above functionality.

Medium::

• Generic List
  • Implement a list similar to how the built-in C# Systems.Collections.Generics.List works.

---

<-- Previous | Next -->