Learning JavaScript Data Structures and Algorithms (2014)

Chapter 2. Arrays

An array is the simplest memory data structure. For this reason, all programming languages have a built-in array data type. JavaScript also supports arrays natively, even though its first version was released without array support. In this chapter, we will dive into the array data structure and its capabilities.

An array stores a sequence of values that are all of the same data type. Although JavaScript allows us to create arrays with values from different data types, we will follow the best practices and consider that we cannot do that (most languages do not have this capability).

Why should we use arrays?

Let's consider that we need to store the average temperature of each month of the year of the city that we live in. We could use something like the following to store this information:

var averageTempJan = 31.9;

var averageTempFeb = 35.3;

var averageTempMar = 42.4;

var averageTempApr = 52;

var averageTempMay = 60.8;

However, this is not the best approach. If we store the temperature for only 1 year, we could manage 12 variables. However, what if we need to store the average temperature for more than 1 year? Fortunately, that is why arrays were created, and we can easily represent the same information mentioned earlier as follows:

averageTemp[0] = 31.9;

averageTemp[1] = 35.3;

averageTemp[2] = 42.4;

averageTemp[3] = 52;

averageTemp[4] = 60.8;

We can also represent the averageTemp array graphically:

Creating and initializing arrays

Declaring, creating, and initializing an array in JavaScript is as simple, as follows:

var daysOfWeek = new Array(); //{1}

var daysOfWeek = new Array(7); //{2}

var daysOfWeek = new Array('Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday'); //{3}

We can simply declare and instantiate a new array by using the keyword new (line {1}). Also, using the keyword new, we can create a new array specifying the length of the array (line {2}). And a third option would be passing the array elements directly to its constructor (line {3}).

However, using the new keyword is not a best practice. If you want to create an array in JavaScript, simply use brackets ([]) like in the following example:

var daysOfWeek = [];

We can also initialize the array with some elements, as follows:

var daysOfWeek = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday'];

If we would like to know how many elements are in the array, we can use the length property. The following code will give an output of 7:

console.log(daysOfWeek.length);

To access a particular position of the array, we also use brackets, passing the numeric position we would like to know the value of or assign a new value to. For example, let's say we would like to output all elements from the daysOfWeek array. To do so, we need to loop the array and print the elements, as follows:

for (var i=0; i<daysOfWeek.length; i++){

console.log(daysOfWeek[i]);

}

Let's take a look at another example. Let's say that we want to find out the first 20 numbers of the Fibonacci sequence. The first two numbers of the Fibonacci sequence are 1 and 2, and each subsequent number is the sum of the previous two numbers:

var fibonacci = []; //{1}

fibonacci[1] = 1; //{2}

fibonacci[2] = 1; //{3}

for(var i = 3; i < 20; i++){

fibonacci[i] = fibonacci[i-1] + fibonacci[i-2]; ////{4}

}

for(var i = 1; i<fibonacci.length; i++){ //{5}

console.log(fibonacci[i]); //{6}

}

So, in line {1}, we are declaring and creating an array. In lines {2} and {3}, we assign the first two numbers of the Fibonacci sequence to the second and third positions of the array (in JavaScript, the first position of the array is always referenced by 0, and as there is no 0 in the Fibonacci sequence, we skip it).

Then, all we have to do is create the third to the twentieth number of the sequence (as we know the first two numbers already). To do so, we can use a loop and assign the sum of the previous two positions of the array to the current position (line {4}—starting from index 3 of the array to the 19th index).

Then, to see the output (line {6}), we just need to loop the array from its first position to its length (line {5}).

Tip

We can use console.log to output each index of the array (lines {5} and {6}) or we can also use console.log(fibonacci) to output the array itself. Most browsers have nice array representation in console.log.

If you would like to generate more than 20 numbers of the Fibonacci sequence, just change the number 20 to whatever number you like.

Adding and removing elements

Adding and removing elements from an array is not that difficult; however, it can be tricky. For the examples we will use in this section, let's consider we have the following numbers array initialized with numbers from 0 to 9:

var numbers = [0,1,2,3,4,5,6,7,8,9];

If we want to add a new element to this array (for example, the number 10), all we have to do is reference the latest free position of the array and assign a value to it:

numbers[numbers.length] = 10;

Note

In JavaScript, an array is a mutable object. We can easily add new elements to it. The object will grow dynamically as we add new elements to it. In many other languages, such as C and Java, we need to determine the size of the array, and if we need to add more elements to the array, we need to create a completely new array; we cannot simply add new elements to it as we need them.

However, there is also a method called push that allows us to add new elements to the end of the array. We can add as many elements as we want as arguments to the push method:

numbers.push(11);

numbers.push(12, 13);

The output of the numbers array will be the numbers from 0 to 13.

Now, let's say we need to add a new element to the array, and we would like to insert it in the first position, not the last one. To do so, first we need to free the first position by shifting all the elements to the right. We can loop all the elements of the array starting from the last position + 1 (length) and shifting the previous element to the new position to finally assign the new value we want to the first position (-1):

for (var i=numbers.length; i>=0; i--){

numbers[i] = numbers[i-1];

}

numbers[0] = -1;

We can represent this action with the following diagram:

The JavaScript array class also has a method called unshift, which inserts the values passed in the method's arguments at the start of the array:

numbers.unshift(-2);

numbers.unshift(-4, -3);

So, using the unshift method, we can add the value -2 and then -3 and -4 to the beginning of the numbers array. The output of this array will be the numbers from -4 to 13.

So far, we have learned how to add values to the end and at the beginning of an array. Let's see how we can remove a value from an array.

To remove a value from the end of an array, we can use the pop method:

numbers.pop();

Tip

The push and pop methods allow an array to emulate a basic stack data structure, which is the subject of the next chapter.

The output of our array will be the numbers from -4 to 12. The length of our array is 17.

To remove a value from the beginning of the array, we can use the following code:

for (var i=0; i<numbers.length; i++){

numbers[i] = numbers[i+1];

}

We can represent the previous code using the following diagram:

We shifted all the elements one position to the left. However, the length of the array is still the same (17), meaning we still have an extra element in our array (with an undefined value).The last time the code inside the loop is executed, i+1 is a reference to a position that does not exist (in some languages, the code would throw an exception and we would have to end our loop at numbers.length -1).

As we can see, we have only overwritten the array's original values, and we did not remove the value for real (as the length of the array is still the same and we have this extra undefined element).

To actually remove an element from the beginning of the array, we can use the shift method as follows:

numbers.shift();

So, if we consider our array has the values -4 to 12 and a length of 17, after we execute the previous code, the array will contain the values -3 to 12 and have a length of 16.

Tip

The shift and unshift methods allow an array to emulate a basic queue data structure, which is the subject of Chapter 4, Queues.

So far, we have learned how to add elements at the end and at the beginning of an array, and we have also learned how to remove elements from the beginning and end of an array. What if we also want to add or remove elements from any particular position of our array? How can we do that?

We can use the splice method to remove an element from an array by simply specifying the position/index we would like to delete from and how many elements we would like to remove:

numbers.splice(5,3);

This code will remove three elements starting from index 5 of our array. This means numbers[5], numbers[6], and numbers[7] will be removed from the numbers array. The content of our array will be -3, -2, -1, 0, 1, 5, 6, 7, 8, 9, 10, 11, and 12 (as numbers 2, 3, and 4 have been removed).

Now, let's say we want to insert numbers 2 to 4 back into the array starting from position 5. We can again use the splice method to do this:

numbers.splice(5,0,2,3,4);

The first argument of the method is the index we want to remove or insert elements from. The second argument is the number of elements we want to remove (in this case, we do not want to remove any, so we pass the value 0 (zero)). And the third argument (and onwards) are the values we would like to insert into the array (elements 2, 3, and 4). The output will be the values from -3 to 12 again.

Finally, let's execute the following code:

numbers.splice(5,3,2,3,4);

The output will be the values from -3 to 12. This is because we are removing three elements starting from index 5 and we are also adding the elements 2, 3, and 4 starting at index 5.

Two-dimensional and multi-dimensional arrays

At the beginning of this chapter, we used the temperature measurement example. We will now use this example one more time. Let's consider that we need to measure the temperature hourly for a few days. Now that we already know that we can use an array to store the temperatures, we can easily write the following code to store the temperatures over two days:

var averageTempDay1 = [72,75,79,79,81,81];

var averageTempDay2 = [81,79,75,75,73,72];

However, this is not the best approach; we can write better code! We can use a matrix (two-dimensional array) to store this information, where each row will represent the day and each column will represent every hourly measurement of the temperature:

var averageTemp = [];

averageTemp[0] = [72,75,79,79,81,81];

averageTemp[1] = [81,79,75,75,73,72];

JavaScript only supports one-dimensional arrays; it does not support matrices. However, we can implement matrices or any multidimensional array by using an array of arrays, as in the previous code. The same code can also be written as follows:

//day 1

averageTemp[0] = [];

averageTemp[0][0] = 72;

averageTemp[0][1] = 75;

averageTemp[0][2] = 79;

averageTemp[0][3] = 79;

averageTemp[0][4] = 81;

averageTemp[0][5] = 81;

//day 2

averageTemp[1] = [];

averageTemp[1][0] = 81;

averageTemp[1][1] = 79;

averageTemp[1][2] = 75;

averageTemp[1][3] = 75;

averageTemp[1][4] = 73;

averageTemp[1][5] = 72;

In the previous code, we are specifying the value of each day and each hour separately. We can also represent this example in a diagram like the following:

Each row represents a day and each column represents an hour of the day (temperature).

If we would like to see the output of the matrix, we can create a generic function to log its output:

function printMatrix(myMatrix) {

for (var i=0; i<myMatrix.length; i++){

for (var j=0; j<myMatrix[i].length; j++){

console.log(myMatrix[i][j]);

}

}

}

We need to loop through all the rows and all the columns. To do this, we need to use a nested for loop, where the variable i represents the rows and j represents the columns.

We can call the following code to see the output of the averageTemp matrix:

printMatrix(averageTemp);

We can also work with multidimensional arrays in JavaScript. For example, let's create a 3 x 3 matrix. Each cell will contain the sum of i (row) + j (column) + z (depth) of the matrix:

var matrix3x3x3 = [];

for (var i=0; i<3; i++){

matrix3x3x3[i] = [];

for (var j=0; j<3; j++){

matrix3x3x3[i][j] = [];

for (var z=0; z<3; z++){

matrix3x3x3[i][j][z] = i+j+z;

}

}

}

It does not matter how many dimensions we have in the data structure; we need to loop each dimension to access the cell. We can represent a 3 x 3 x 3 matrix with a cube diagram, as follows:

To output the content of this matrix, we can use the following code:

for (var i=0; i<matrix3x3x3.length; i++){

for (var j=0; j<matrix3x3x3[i].length; j++){

for (var z=0; z<matrix3x3x3[i][j].length; z++){

console.log(matrix3x3x3[i][j][z]);

}

}

}

If we had a 3 x 3 x 3 x 3 matrix, we would have four nested for statements in our code, and so on.

References for JavaScript array methods

Arrays in JavaScript are modified objects, meaning that every array that we create has a few methods available to be used. JavaScript arrays are very interesting because they are very powerful and have more capabilities available than the primitive arrays of other languages. This means that we do not need to write basic capabilities ourselves, such as adding and removing elements in/from the middle of the data structure.

The following is a list of the core available methods in an array object. We have covered some methods already.

We have already covered the push, pop, shift, unshift, and splice methods. Let's take a look at these new ones. These methods will be very useful in the subsequent chapters of this book where we will code our own data structure and algorithms.

Joining multiple arrays

Consider a scenario where you have different arrays and you need to join all of them into a single array. We could iterate each array and add each element to the final array. Fortunately, JavaScript already has a method that can do that for us, named the concat method:

var zero = 0;

var positiveNumbers = [1,2,3];

var negativeNumbers = [-3,-2,-1];

var numbers = negativeNumbers.concat(zero, positiveNumbers);

We can pass as many arrays and objects/elements to this array as we desire. The arrays will be concatenated to the specified array in the order the arguments are passed to the method. In this example, zero will be concatenated to negativeNumbers, and then positiveNumbers will be concatenated to the resulting array. The output of the numbers array will be the values -3, -2, -1, 0, 1, 2, and 3.

Iterator functions

Sometimes we need to iterate the elements of an array. We have learned that we can use a loop construct to do this, such as the for statement, as we saw in some previous examples.

JavaScript also has some built-in iterator methods that we can use with arrays. For the examples of this section, we will need an array and also a function. We will use an array with values from 1 to 15, and also a function that returns true if the number is a multiple of 2 (even), and falseotherwise:

var isEven = function (x) {

// returns true if x is a multiple of 2.

console.log(x);

return (x % 2 == 0) ? true : false;

};

var numbers = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

return (x % 2 == 0) ? true : false can also be represented as return (x % 2 == 0).

The first method we will take a look at is the every method. The every method will iterate each element of the array until the return of the function is false:

numbers.every(isEven);

In this case, our first element of the numbers array is the number 1. 1 is not a multiple of 2 (it is an odd number), so the isEven function will return false and this will be the only time the function will be executed.

Next, we have the some method. It has the same behavior as the every method, however, the some method will iterate each element of the array until the return of the function is true:

numbers.some(isEven);

In our case, the first even number of our numbers array is 2 (the second element). The first element that will be iterated is number 1; it will return false. Then, the second element that will be iterated is number 2, and it will return true—and the iteration will stop.

If we need the array to be completely iterated no matter what, we can use the forEach function. It has the same result as using a for loop with the function's code inside it:

numbers.forEach(function(x){

console.log((x % 2 == 0));

});

JavaScript also has two other iterator methods that return a new array with a result. The first one is the map method:

var myMap = numbers.map(isEven);

The myMap array will have the following values: [false, true, false, true, false, true, false, true, false, true, false, true, false, true, false]. It stores the result of the isEven function that was passed to the map method. This way, we can easily know whether a number is even or not. For example, myMap[0] returns false because 1 is not even and myMap[1] returns true because 2 is even.

We also have the filter method. It returns a new array with the elements that the function returned true:

var evenNumbers = numbers.filter(isEven);

In our case, the evenNumbers array will contain the elements that are multiples of 2: [2, 4, 6, 8, 10, 12, 14].

Finally, we have the reduce method. The reduce method also receives a function with the following parameters: previousValue, currentValue, index, and array. We can use this function to return a value that will be added to an accumulator, which is going to be returned after the reducemethod stops being executed. It can be very useful if we want to sum up all the values in an array, for example:

numbers.reduce(function(previous, current, index){

return previous + current;

});

The output is going to be 120.

Searching and sorting

Throughout this book, we will learn how to write the most used searching and sorting algorithms. However, JavaScript also has a sorting method and a couple of searching methods available. Let's take a look at them.

First, let's take our numbers array and put the elements out of order (1, 2, 3, … 15 is already sorted). To do that, we can apply the reverse method, where the last item will be the first and vice versa:

numbers.reverse();

So now, the output for the numbers array will be the following: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Then, we can apply the sort method:

numbers.sort();

However, if we output the array, the result will be [1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9]. This is not ordered correctly. This is because the sort method sorts the elements lexicographically and it assumes all the elements are strings.

We can also write our own comparison function. As our array has numeric elements, we can write the following code:

numbers.sort(function(a,b){

return a-b;

});

This code will return a negative number if b is bigger than a, a positive number if a is bigger than b, and zero if they are equal. This means that if a negative value is returned, it implies that a is smaller than b, which is further used by the sort function to arrange the elements.

The previous code can be represented by the following code as well:

function compare(a, b) {

if (a < b) {

return -1;

}

if (a > b) {

return 1;

}

// a must be equal to b

return 0;

}

numbers.sort(compare);

This is because the sort function from the JavaScript Array class can receive a parameter called compareFunction, which will be responsible for sorting the array. In our example, we declared a function that will be responsible for comparing the elements of the array, resulting in an array sorted in ascending order.

Custom sorting

We can sort an array with any type of object in it, and we can also create a compareFunction to compare the elements as we need to. For example, suppose we have an object, Person, with name and age and we want to sort the array based on the age of the person; we can use the following code:

var friends = [

{name: 'John', age: 30},

{name: 'Ana', age: 20},

{name: 'Chris', age: 25}

];

function comparePerson(a, b){

if (a.age < b.age){

return -1

}

if (a.age > b.age){

return 1

}

return 0;

}

console.log(friends.sort(comparePerson));

In this case, the output from the previous code will be Ana (20), Chris (25), and John (30).

Sorting strings

Suppose we have the following array:

var names =['Ana', 'ana', 'john', 'John'];

console.log(names.sort());

What do you think is going to be the output? The answer is as follows:

["Ana", "John", "ana", "john"]

Why does ana come after John, since "a" comes first in the alphabet? The answer is because JavaScript compares each character according to its ASCII value. For example, A, J, a, and j have the decimal ASCII values of A: 65, J: 74, a: 97, and j: 106.

Therefore, J has a lower value than a, and because of this, it comes first in the alphabet.

Note

For more information about the ASCII table, please visit http://www.asciitable.com/.

Now, if we pass a compareFunction that contains the code to ignore the case of the letter, we will have the output ["Ana", "ana", "John", "john"], as follows:

names.sort(function(a, b){

if (a.toLowerCase() < b.toLowerCase()){

return -1

}

if (a.toLowerCase() > b.toLowerCase()){

return 1

}

return 0;

});

For accented characters, we can use the localeCompare method as well:

var names2 = ['Maève', 'Maeve'];

console.log(names2.sort(function(a, b){

return a.localeCompare(b);

}));

And the output will be ["Maeve", "Maève"].

Searching

We have two options for searching: the indexOf method, which returns the index of the first element that matches the argument passed, and lastIndexOf, which returns the index of the last element found that matches the argument passed. Let's go back to the numbers array we were using before:

console.log(numbers.indexOf(10));

console.log(numbers.indexOf(100));

In the previous example, the output in the console will be 9 for the first line and -1 (because it does not exist in our array) for the second line.

We get the same result with the following code:

numbers.push(10);

console.log(numbers.lastIndexOf(10));

console.log(numbers.lastIndexOf(100));

We added a new element with a value of 10, so the second line will output 15 (our array now has values from 1 to 15 + 10), and the third line outputs -1 (because the element 100 does not exist in our array).

Outputting the array into a string

Finally, we come to the final two methods: toString and join.

If we would like to output all the elements of the array into a single string, we can use the toString method as follows:

console.log(numbers.toString());

This will output the values 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, and 10 to the console.

If we would like to separate the elements by a different separator, such as -, we can use the join method to do just that:

var numbersString = numbers.join('-');

console.log(numbersString);

The output will be as follows:

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-10

This can be useful if we need to send the array's content to a server or to be decoded (and then, knowing the separator, it is easy to decode).

Note

There are some great resources that you can use to boost your knowledge about arrays and their methods:

· The first one is the arrays page from w3schools at http://www.w3schools.com/js/js_arrays.asp

· The second one is the array methods page from w3schools at http://www.w3schools.com/js/js_array_methods.asp

· Mozilla also has a great page about arrays and their methods with great examples at https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array (http://goo.gl/vu1diT)

· There are also great libraries that are very useful when working with arrays in JavaScript projects:

o The Underscore library: http://underscorejs.org/

o The Lo-Dash library: http://lodash.com/

Summary

In this chapter, we covered the most used data structure: arrays. We learned how to declare, initialize, and assign values as well as add and remove elements. We also learned about two-dimensional and multi-dimensional arrays as well as the main methods of an array, which will be very useful when we start creating our own algorithms in later chapters.

In the next chapter, we will learn about stacks, an array with a special behavior.