JavaScript basics

Before we start diving in to the various data structures and algorithms, let's have a quick overview of the JavaScript language. This section will present the JavaScript basics required to implement the algorithms we will create in the subsequent chapters.

To start, let's look at the two different ways we can use JavaScript code on an HTML page. The first example is demonstrated by the following code. We need to create an HTML file (01-HelloWorld.html) and write this code in it. In this example, we are declaring the script tag inside the HTML file and, inside the script tag, we have the JavaScript code:

<!DOCTYPE html> 
<html> 
  <head> 
    <meta charset="UTF-8"> 
  </head> 
  <body> 
    <script> 
      alert('Hello, World!'); 
    </script> 
  </body> 
</html>

Try using the Web Server for Chrome extension or the http-server to run the preceding code and see its output in the browser.

For the second example, we need to create a JavaScript file (we can save it as 01- HelloWorld.js) and, inside this file, we will insert the following code:

alert('Hello, World!');

Then, our HTML file will look similar to this:

<!DOCTYPE html> 
<html> 
  <head> 
    <meta charset="UTF-8"> 
    <title></title> 
  </head> 
  <body> 
    <script src="01-HelloWorld.js"></script> 
  </body> 
</html>

The second example demonstrates how to include a JavaScript file inside an HTML file.

By executing any of these two examples, the output will be the same. However, the second example is the most used by JavaScript developers.

You may find JavaScript include statements or JavaScript code inside the head tag in some examples on the internet. As a best practice, we will include any JavaScript code at the end of the body tag. This way, the HTML will be parsed by the browser and displayed before the scripts are loaded. This boosts the performance of the page.

Variables

Variables store data that can be set, updated, and retrieved whenever necessary. Values that are assigned to a variable belong to a type. In JavaScript, the available types are number, string, boolean, function, and object. We also have undefined and null, along with arrays, dates, and regular expressions.

Although JavaScript has different available variable types, it is not a strongly typed language such as C/C++, C#, and Java. In strongly typed languages, we need to declare the type of the variable along with its declaration (for example, in Java, to declare an integer variable, we use int num = 1;). In JavaScript, we only need to use the keyword var, and we do not need to declare the variable type. For this reason, JavaScript is not a strongly typed language. However, there are discussions and a specification in draft mode for optional static typing (https://github.com/dslomov/typed-objects-es7) that can become part of the JavaScript specification (ECMAScript) in the future. We can also use TypeScript in case we want to type our variables when working with JavaScript. We will learn more about ECMAScript and TypeScript later in this chapter.

The following is an example of how to use variables in JavaScript:

var num = 1; // {1} 
num = 3; // {2} 
var price = 1.5; // {3} 
var myName = 'Packt'; // {4} 
var trueValue = true; // {5} 
var nullVar = null; // {6} 
var und; // {7}

In line {1}, we have an example of how to declare a variable in JavaScript (we are declaring a number). Although it is not necessary to use the var keyword declaration, it is a good practice to always specify when we declare a new variable.
In line {2}, we updated an existing variable. JavaScript is not a strongly typed language. This means you can declare a variable, initialize it with a number, and then update it with a string or any other datatype. Assigning a value to a variable that is different from its original type is also not a good practice.
In line {3}, we also declared a number, but this time it is a decimal floating point. In line {4}, we declared a string; in line {5}, we declared a boolean. In line {6}, we declared a null value, and in line {7}, we declared an undefined variable. A null value means no value, and undefined means a variable that has been declared but not yet assigned a value.

If we want to see the value of each variable we declared, we can use console.log to do so, as listed in the following code snippet:

console.log('num: ' + num); 
console.log('myName: ' + myName); 
console.log('trueValue: ' + trueValue); 
console.log('price: ' + price); 
console.log('nullVar: ' + nullVar); 
console.log('und: ' + und);

The console.log method also accepts more than just arguments. Instead of console.log('num: ' + num), we can also use console.log('num: ', num). While the first option is going to concatenate the result into a single string, the second option allows us to add a description and also visualize the variable content in case it is an object.

We have three ways of outputting values in JavaScript that we can use with the examples of this book. The first one is alert('My text here'), which outputs an alert window on the browser, and the second one is console.log('My text here'), which outputs text on the Console tab of the debug tool (Google Developer Tools or Firebug, depending on the browser you are using). The third way is outputting the value directly on the HTML page that is rendered by the browser using document.write('My text here'). You can use the option that you feel most comfortable with.

We will discuss functions and objects later in this chapter.

Scope variable

The scope refers to where in the algorithm we can access the variable (it can also be a function when we work with function scopes). There are local and global variables.

Let's look at an example:

var myVariable = 'global'; 
myOtherVariable = 'global'; 
 
function myFunction() { 
  var myVariable = 'local'; 
  return myVariable; 
} 
 
function myOtherFunction() { 
  myOtherVariable = 'local'; 
  return myOtherVariable; 
} 
 
console.log(myVariable); //{1} 
console.log(myFunction()); //{2} 
 
console.log(myOtherVariable); //{3} 
console.log(myOtherFunction()); //{4} 
console.log(myOtherVariable); //{5}

The above code can be explained as follows:

Line {1} will output global because we are referring to a global variable.
Line {2} will output local because we declared the myVariable variable inside the myFunction function as a local variable, so the scope will only be inside myFunction.
Line {3} will output global because we are referencing the global variable named myOtherVariable that was initialized on the second line of the example.
Line {4} will output local. Inside the myOtherFunction function, we referenced the myOtherVariable global variable and assigned the value local to it because we are not declaring the variable using the var keyword.
For this reason, line {5} will output local (because we changed the value of the variable inside myOtherFunction).

You may hear that global variables in JavaScript are evil, and this is true. Usually, the quality of JavaScript source code is measured by the number of global variables and functions (a large number is bad). So, whenever possible, try avoiding global variables.

Operators

We need operators when performing any operation in a programming language. JavaScript also has arithmetic, assignment, comparison, logical, bitwise, and unary operators, among others. Let's take a look at these:

var num = 0; // {1}  
num = num + 2; 
num = num * 3;  
num = num / 2;  
num++; 
num--; 
 
num += 1; // {2} 
num -= 2; 
num *= 3; 
num /= 2; 
num %= 3; 
 
console.log('num == 1 : ' + (num == 1)); // {3}  
console.log('num === 1 : ' + (num === 1));  
console.log('num != 1 : ' + (num != 1));  
console.log('num > 1 : ' + (num > 1)); 
console.log('num < 1 : ' + (num < 1));  
console.log('num >= 1 : ' + (num >= 1));  
console.log('num <= 1 : ' + (num <= 1)); 
 
console.log('true && false : ' + (true && false)); // {4}  
console.log('true || false : ' + (true || false));  
console.log('!true : ' + (!true));

In line {1}, we have the arithmetic operators. In the following table, we have the operators and their descriptions:

Arithmetic operator	Description
+	Addition
-	Subtraction
*	Multiplication
/	Division
%	Modulus (remainder of a division operation)
++	Increment
--	Decrement

In line {2}, we have the assignment operators. In the following table, we have the operators and their descriptions:

Assignment operator	Description
=	Assignment
+=	Addition assignment (x += y) == (x = x + y)
-=	Subtraction assignment (x -= y) == (x = x - y)
*=	Multiplication assignment (x = y) == (x = x y)
/=	Division assignment (x /= y) == (x = x / y)
%=	Remainder assignment (x %= y) == (x = x % y)

In line {3}, we have the comparison operators. In the following table, we have the operators and their descriptions:

Comparison operator	Description
==	Equal to
===	Equal to (both value and object type)
!=	Not equal to
>	Greater than
>=	Greater than or equal to
<	Less than
<=	Less than or equal to

Finally, in line {4}, we have the logical operators. In the following table, we have the operators and their descriptions:

Logical operator	Description
&&	And
\|\|	Or
!	Not

JavaScript also supports bitwise operators, which are shown as follows:

console.log('5 & 1:', (5 & 1)); 
console.log('5 | 1:', (5 | 1)); 
console.log('~ 5:', (~5)); 
console.log('5 ^ 1:', (5 ^ 1)); 
console.log('5 << 1:', (5 << 1)); 
console.log('5 >> 1:', (5 >> 1));

The following table contains a more detailed description of the bitwise operators:

Bitwise operator	Description
&	And
\|	Or
~	Not
^	Xor
<<	Left shift
>>	Right shift

The typeof operator returns the type of the variable or expression. For example, have a look at the following code:

console.log('typeof num:', typeof num); 
console.log('typeof Packt:', typeof 'Packt'); 
console.log('typeof true:', typeof true); 
console.log('typeof [1,2,3]:', typeof [1,2,3]); 
console.log('typeof {name:John}:', typeof {name:'John'});

The output will be as follows:

    typeof num: number
    typeof Packt: string
    typeof true: boolean
    typeof [1,2,3]: object
    typeof {name:John}: object

According to the specification, there are two data types in JavaScript:

Primitive data types: Null, undefined, string, number, boolean, and symbol
Derived data types/objects: JavaScript objects, including functions, arrays, and regular expressions

JavaScript also supports the delete operator, which deletes a property from an object:

var myObj = {name: 'John', age: 21}; 
delete myObj.age; 
console.log(myObj); //outputs Object {name: "John"}

In this book's algorithms, we will be using some of these operators.

Truthy and falsy

In JavaScript, true and false are a little bit tricky. In most languages, the boolean values true and false represent the true/false results. In JavaScript, a string such as Packt evaluates to true.

The following table can help us better understand how true and false work in JavaScript:

Value Type	Result
`undefined`	`false`
`null`	`false`
Boolean	true is `true` and false is `false`
Number	The result is `false` for `+0`, `-0`, or `NaN`; otherwise, the result is `true`
String	The result is `false` if the string is empty (length is 0); otherwise, the result is `true` (length >= 1)
Object	`true`

Let's consider some examples and verify their output:

function testTruthy(val) { 
  return val ? console.log('truthy') : console.log('falsy'); 
} 
 
testTruthy(true); // true 
testTruthy(false); // false 
testTruthy(new Boolean(false)); // true (object is always true) 
 
testTruthy(''); // false 
testTruthy('Packt'); // true 
testTruthy(new String('')); // true (object is always true) 
 
testTruthy(1); // true 
testTruthy(-1); // true 
testTruthy(NaN); // false 
testTruthy(new Number(NaN)); // true (object is always true) 
 
testTruthy({}); // true (object is always true) 
 
var obj = { name: 'John' }; 
testTruthy(obj); // true 
testTruthy(obj.name); // true 
testTruthy(obj.age); // age (property does not exist)

Functions of the equals operators (== and ===)

The two equals operators supported by JavaScript can cause a little bit of confusion when working with them.

When using ==, values can be considered equal even when they are of different types. This can be confusing even for a senior JavaScript developer. Let's analyze how == works using the following table:

Type(x)	Type(y)	Result
null	undefined	`true`
undefined	null	`true`
Number	String	`x == toNumber(y)`
String	Number	`toNumber(x) == y`
Boolean	Any	`toNumber(x) == y`
Any	Boolean	`x == toNumber(y)`
String or Number	Object	`x == toPrimitive(y)`
Object	String or number	`toPrimitive(x) == y`

If x and y are of the same type, then JavaScript will use the equals method to compare the two values or objects. Any other combination that is not listed in the table gives a false result.

The toNumber and toPrimitive methods are internal and evaluate the values according to the tables that follow.

The toNumber method is as follows:

Value type	Result
`undefined`	This is `NaN`
`null`	This is `+0`
Boolean	If the value is `true`, the result is `1`; if the value is `false`, the result is `+0`
Number	This is the value of the number

Finally, toPrimitive is as follows:

Value Type	Result
Object	If `valueOf` returns a primitive value, it returns the primitive value; otherwise, if `toString` returns a primitive value, it returns the primitive value and otherwise returns an error

Let's verify the results of some examples. First, we know that the output of the following code is true (string length > 1):

console.log('packt' ? true : false);

Now, what about the following code? Let's take a look:

console.log('packt' == true);

The output is false, so let's understand why:

First, it converts the boolean value using toNumber, so we have packt == 1.
Then, it converts the string value using toNumber. Since the string consists of alphabetical characters, it returns NaN, so we have NaN == 1, which is false.

What about the following code? Let's take a look:

console.log('packt' == false);

The output is also false, and the following is why:

First, it converts the boolean value using toNumber, so we have packt == 0.
Then, it converts the string value using toNumber. Since the string consists of alphabetical characters, it returns NaN, so we have NaN == 0, which is false.

What about the === operator? This is much easier. If we are comparing two values of different types, the result is always false. If they have the same type, they are compared according to the following table:

Type(x)	Values	Result
Number	`x` has the same value as `y` (but not `NaN`)	`true`
String	`x` and `y` are identical characters	`true`
Boolean	`x` and `y` are both `true` or both `false`	`true`
Object	`x` and `y` reference the same object	`true`

If x and y are different types, then the result is false. Let's consider some examples:

console.log('packt' === true); //false  
console.log('packt' === 'packt'); //true 
var person1 = {name:'John'};  
var person2 = {name:'John'}; 
console.log(person1 === person2); //false, different objects

Control structures

JavaScript has a similar set of control structures as the C and Java languages. Conditional statements are supported by if...else and switch. Loops are supported by the while, do...while, and for constructs.

Conditional statements

The first conditional statement we will take a look at is the if...else construct. There are a few ways we can use the if...else construct.

We can use the if statement if we want to execute a block of code only if the condition (expression) is true, as follows:

var num = 1; 
if (num === 1) { 
  console.log('num is equal to 1'); 
}

We can use the if...else statement if we want to execute a block of code and the condition is true or another block of code just in case the condition is false (else), as follows:

var num = 0; 
if (num === 1) { 
  console.log('num is equal to 1'); 
} else { 
  console.log('num is not equal to 1, the value of num is ' + num); 
}

The if...else statement can also be represented by a ternary operator. For example, take a look at the following if...else statement:

if (num === 1) { 
  num--; 
} else { 
  num++; 
}

It can also be represented as follows:

(num === 1) ? num-- : num++;

Also, if we have several expressions, we can use if...else several times to execute different blocks of code based on different conditions, as follows:

var month = 5; 
if (month === 1) { 
  console.log('January'); 
} else if (month === 2) { 
  console.log('February'); 
} else if (month === 3) { 
  console.log('March'); 
} else { 
  console.log('Month is not January, February or March'); 
}

Finally, we have the switch statement. If the condition we are evaluating is the same as the previous one (however, it is being compared to different values), we can use the switch statement:

var month = 5; 
switch (month) { 
  case 1: 
    console.log('January'); 
    break; 
  case 2: 
    console.log('February'); 
    break; 
  case 3: 
    console.log('March'); 
    break; 
  default: 
    console.log('Month is not January, February or March'); 
}

One thing that is very important in a switch statement is the use of the case and break keywords. The case clause determines whether the value of switch is equal to the value of the case clause. The break statement stops the switch statement from executing the rest of the statement (otherwise, it will execute all the scripts from all case clauses below the matched case until a break statement is found in one of the case clauses). Finally, we have the default statement, which is executed by default if none of the case statements are true (or if the executed case statement does not have the break statement).

Loops

Loops are often used when we work with arrays (which are the subject of the next chapter). Specifically, we use the for loop in our algorithms.

The for loop is the same as in C and Java. It consists of a loop counter that is usually assigned a numeric value, then the variable is compared against another value (the script inside the for loop is executed while this condition is true), and finally, the numeric value is increased or decreased.

In the following example, we have a for loop. It outputs the value of i on the console, where i is less than 10; i is initiated with 0, so the following code will output the values 0 to 9:

for (var i = 0; i < 10; i++) { 
  console.log(i); 
}

The next loop construct we will look at is the while loop. The block of code inside the while loop is executed while the condition is true. In the following code, we have a variable, i, initiated with the value 0, and we want the value of i to be output while i is less than 10 (or less than or equal to 9). The output will be the values from 0 to 9:

var i = 0; 
while (i < 10) { 
  console.log(i); 
  i++; 
}

The do...while loop is similar to the while loop. The only difference is that in the while loop, the condition is evaluated before executing the block of code, and in the do...while loop, the condition is evaluated after the block of code is executed. The do...while loop ensures that the block of code is executed at least once. The following code also outputs the values from 0 to 9:

var i = 0; 
do { 
  console.log(i); 
  i++; 
} while (i < 10);

Functions

Functions are very important when working with JavaScript. We will also use functions in our examples.

The following code demonstrates the basic syntax of a function. It does not have arguments or the return statement:

function sayHello() { 
  console.log('Hello!'); 
}

To execute this code, we simply use the following statement:

sayHello();

We can also pass arguments to a function. Arguments are variables with which a function is supposed to do something. The following code demonstrates how to use arguments with functions:

function output(text) { 
  console.log(text); 
}

To use this function, we can use the following code:

output('Hello!');

You can use as many arguments as you like, as follows:

output('Hello!', 'Other text');

In this case, only the first argument is used by the function, and the second one is ignored. A function can also return a value, as follows:

function sum(num1, num2) { 
  return num1 + num2; 
}

This function calculates the sum of two given numbers and returns its result. We can use it as follows:

var result = sum(1, 2); 
output(result); // outputs 3

Object-oriented programming in JavaScript

JavaScript objects are very simple collections of name-value pairs. There are two ways of creating a simple object in JavaScript. The first way is as follows:

var obj = new Object();

And the second way is as follows:

var obj = {};

We can also create an entire object, as follows:

obj = { 
  name: { 
    first: 'Gandalf', 
    last: 'the Grey' 
  }, 
  address: 'Middle Earth' 
};

As we can see, to declare a JavaScript object, [key, value] pairs are used, where the key can be considered an attribute of the object and the value is the property value. All classes that we will create in this book are JavaScript objects, such as Stack, Set, LinkedList, Dictionary, Tree, Graph, and so on.

In Object-oriented programming (OOP), an object is an instance of a class. A class defines the characteristics of the object. For our algorithms and data structures, we will create some classes that will represent them. This is how we can declare a class (constructor) that represents a book:

function Book(title, pages, isbn) { 
  this.title = title; 
  this.pages = pages; 
  this.isbn = isbn; 
}

To instantiate this class, we can use the following code:

var book = new Book('title', 'pag', 'isbn');

Then, we can access its properties and update them as follows:

console.log(book.title); // outputs the book title 
book.title = 'new title'; // update the value of the book title 
console.log(book.title); // outputs the updated value

A class can also contain functions (generally also referred to as methods). We can declare and use a function/method as the following code demonstrates:

Book.prototype.printTitle = function() { 
  console.log(this.title); 
}; 
 
book.printTitle();

We can declare functions directly inside the class definition as well:

function Book(title, pages, isbn) { 
  this.title = title; 
  this.pages = pages; 
  this.isbn = isbn; 
  this.printIsbn = function() { 
    console.log(this.isbn); 
  }; 
} 
book.printIsbn();

In the prototype example, the printTitle function will be shared between all the instances and only one copy will be created. When we use a class-based definition, as in the previous example, each instance will have its own copy of the functions. Using the prototype method saves memory and processing cost regarding assigning the functions to the instance. However, you can only declare public functions and properties using the prototype method. With a class-based definition, you can declare private functions and properties, and the other methods inside the class can also access them. ECMAScript 2015 (ES6) introduces a simplified syntax like the class-based example and it is prototype-based. We will discuss more on this later in this chapter.