Book Image

Learning JavaScript Data Structures and Algorithms - Second Edition

By : Loiane Groner
Book Image

Learning JavaScript Data Structures and Algorithms - Second Edition

By: Loiane Groner

Overview of this book

This book begins by covering basics of the JavaScript language and introducing ECMAScript 7, before gradually moving on to the current implementations of ECMAScript 6. You will gain an in-depth knowledge of how hash tables and set data structure functions, as well as how trees and hash maps can be used to search files in a HD or represent a database. This book is an accessible route deeper into JavaScript. Graphs being one of the most complex data structures you’ll encounter, we’ll also give you a better understanding of why and how graphs are largely used in GPS navigation systems in social networks. Toward the end of the book, you’ll discover how all the theories presented by this book can be applied in real-world solutions while working on your own computer networks and Facebook searches.
Table of Contents (18 chapters)
Learning JavaScript Data Structures and Algorithms - Second Edition
Credits
About the Author
About the Reviewer
www.PacktPub.com
Preface

JavaScript basics


Before we start diving into 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 take a look at the two different ways we can use JavaScript code on an HTML page:

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

The first way is demonstrated by the previous code. We need to create an HTML file and write this code on it. In this example, we are declaring the script tag inside the HTML file and, inside the script tag, we have the JavaScript code.

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"> 
  </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 best practice.

Note

You may find JavaScript include statements or JavaScript code inside the head tag in some examples on the Internet. As 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 needed. Values that are assigned to a variable belong to a type. In JavaScript, the available types are numbers, strings, Booleans, functions, and objects. We also have undefined and null, along with arrays, dates, and regular expressions.

Note

Although JavaScript has different available variable types, it is not a strongly typed language such as C/C++, C#, Java. In strongly typed languages, we need to declare the type of the variable along with its declaration (in Java, for example, 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.

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 name = 'Packt'; //{4} 
var trueValue = true; //{5} 
var nullVar = null; //{6} 
var und;  //{7} 
  • On 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 good practice to always specify when we declare a new variable.

  • On 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 good practice.

  • On line {3}, we also declared a number, but this time it is a decimal floating point. On line {4}, we declared a string; on line {5}, we declared a Boolean. On line {6}, we declared a null value, and on 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. Take a look at the following:

        console.log("num: "+ num); 
        console.log("name: "+ name); 
        console.log("trueValue: "+ trueValue); 
        console.log("price: "+ price); 
        console.log("nullVar: "+ nullVar); 
        console.log("und: "+ und); 

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

Note

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.

The console.log method also accepts more than just arguments. Instead of console.log("num: "+ num), we can also use console.log("num: ", num).

We will discuss functions and objects later in this chapter.

Variable scope

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} 
  • 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  referencing the myOtherVariable global variable and assigning 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)); 

On 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

On 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)

On 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 (value and object type both)

!=

Not equal to

>

Greater than

>=

Greater than or equal to

<

Less than

<=

Less than or equal to

Finally, on 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

JavaScript also supports the delete operator, which deletes a property from an object. Take a look at the following code:

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

In this book's algorithms, we will use 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" has the value true, for example.

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); //false (age does not exist) 

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

The two equal 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 presented here:

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.

String

This parses the string into a number. If the string consists of alphabetical characters, the result is NaN; if the string consists of numbers, it is transformed into a number.

Object

This is toNumber(toPrimitive(value)).

Finally, toPrimitive is presented here:

Value type

Result

Object

If valueOf returns a primitive value, this returns the primitive value; otherwise, if toString returns a primitive value, this 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. As 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 are the steps:

  • First, it converts the Boolean value using toNumber, so we have packt == 0.

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

What about the === operator? It 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