 # Learn Data Structure and Algorithm in JavaScript | Part 04 Edison Pebojot(👨‍💻) Updated on ・19 min read

# Prerequisite (✋😐)

01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String object’s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(❗) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(😉)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (💡).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (👀). (😃)
11 Hash Tables A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (😃)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (🔈)) not (kwewe) okay? hehehe (😅); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (😃) Let's go! (🔥🔥🔥)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (😮) There are two types of linked lists: singly (➡️) and doubly (↔️). Let’s examine the singly linked list first.(😃) Let's go! (🔥🔥🔥)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (😃)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (👍)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (😉)
19 Dynamic Programming Dynamic programming involves breaking down problems into their subproblems. Solving the subproblems and saving those results into memory to access them whenever a repeated problem needs to be solved, the algorithmic complexity decreases significantly (⬇️). To explain dynamic programming, let’s re examine the Fibonacci sequence that was discussed in Part 8. Then Part 19 will cover the rules of dynamic programming and walk you through some examples to make the concepts more concrete. (😉)
20 Bit Manipulation Bit manipulation is an advanced topic that JavaScript developers typically do not need to know. However, you should learn a bit about bit manipulation if you want to implement high-performance server-side code. Understanding bit manipulation requires some knowledge of digital logic. Any introductory course in discrete math or circuits would be helpful to understand these concepts.

# Part 04: JavaScript Strings(😱 🔥 🔠) This part 4 will focus on strings, JavaScript String object, and the String object’s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption. By the end of this part, you will understand how to effectively work with JavaScript strings and have a fundamental understanding of string encoding and encryption. (🔒)

## JavaScript String Primitive (🔤) JavaScript’s String primitive comes with various common string functions.

### String Access (🔓)

For accessing characters, you use .chartAt():

   'dog'.charAt(1); // returns "o" 

.charAt( index ) takes an index (which starts at 0) and returns the character at that index location in the string.

For multiple-character access, you can use .substring( startIndex, endIndex ), which will return the characters between indices:

   console.log('YouTube'.substring(1,2)) // returns 'o' console.log('YouTube'.substring(3,7)) // returns 'tube' 

If you do not pass a second parameter (startIndex, endIndex), it will return all the character values:

   'YouTube'.substring(0); // returns 'Youtube' 

### String Comparison ( $=$ )

Programming languages have a function that allows you to compare strings. In JavaScript, this can be done simply by using less-than (<) and greater-than (>) operators:

   'a' < 'b' // prints 'true' 

This can be really useful for comparing strings when sorting algorithms, which is covered later in part 10. However, if you are comparing two strings of different lengths, it starts comparing from the start of the string:

   'abc' < 'b' // prints 'true' 

Since add is smaller than b, abc < b evaluates to true:

   'add' < 'ab' // prints 'false' 

In this example, a d d and a b are compared. This is the
same as comparing ad with ab:

   'add'<'ab' == 'ad'<'ab' // prints 'true' 

### String Search (🔍🔍🔍)

To find a specific string within a string, you can use .indexOf ( searchValue [ , fromIndex ] ) . This takes the string to be searched as well as the starting index for the search. It returns the position of the
matching string, but if found nothing, then -1 (negative one) is returned:

   // Return positive numbers console.log('Red Dragon'.indexOf('Red')) // returns 0 console.log('Red Dragon'.indexOf('Dragon', 0)) // returns 4 console.log('Red Dragon'.indexOf('Dragon', 4)) // returns 4 console.log('Red Dragon'.indexOf("", 9)) // returns 9 // Return negative number console.log('Red Dragon'.indexOf('RedScale')) // returns -1 

To search string inside a larger string, simply check -1 from .indexOf :

   let existsInString=(stringValue, search)=> stringValue.indexOf(search) !== -1; console.log(existsInString('Let say I am the largest string', 'r')); // prints 'true'; console.log(existsInString('Let say I am the largest string', 'b')); // prints 'false'; 

In the following example, the occurrences of the character a will be counted:

   // This will count how many 'a' inside the string ((str="He's my king from this day until his last day")=>Array.from(str).map((v,i)=>v=='a'?str.indexOf('a')!==-1?0+1:0:0).filter((v=>v)).length)() 

Finally, startsWith returns true (boolean) if the string starts with the input, and endsWith checks whether the string ends with the input:

   console.log('Red Dragon'.startsWith('Red')) // returns true console.log('Red Dragon'.endsWith('Dragon')) // returns true console.log('Red Dragon'.startsWith('Dragon')) // returns false console.log('Red Dragon'.endsWith('Red')) // returns false 

### String Decomposition (💩💩💩)

For decomposing a string into parts, you can use .split( separator ) . It creates an array of substrings:

   'chicken,noodle,soup,broth'.split(","); // ["chicken", "noodle", "soup", "broth"] 

Passing an empty separator will create an array of:

   'chicken'.split(""); // // ["c", "h", "i", "c", "k", "e", "n"] 

The string can be turned into an array to easily iterate through them:

   'chicken'.split("").forEach(v=>console.log(v)) 

### String Replace (✂️✂️✂️)

.replace( string , replaceString ) replaces a string with another string:

   "Wizard of Oz".replace("Wizard","Witch"); // "Witch of Oz" 

## Regular Expressions (😛😲😱😆) Regular expressions (or regexes) define a search pattern. JavaScript comes with object RegExp, which is used for regular expressions.

The constructor for RegExp object takes two parameters: the regular expression and the optional match settings, as shown here:

i. Perform case-insensitive matching
g. Perform a global match (find all matches rather than stopping after
first match)
m. Perform multiline matching


RegExp has two functions:

• search(): returns the index of the match.
• match(): returns all the matches.

JavaScript String object also has the following two regex-related functions that accept the RegExp object:

• exec(): returns the first match.
• test(): returns true or false.

### Basic Regex (👌👌👌)

Here are the basic regex rules:

• ^: Indicates the start of a string
• \d: Finds any digit
• [abc]: Finds any character between the brackets
• [^abc]: Finds any character not between the brackets
• [0-9]: Finds any digit between the brackets
• [^0-9]: Finds any digit not between the brackets
• (x|y): Finds any of the alternatives

The following returns index 11, which is the index of the character D, which is the first character of the matched regex:

   "JavaScript DataStructures".search(/DataStructures/) // prints '11' 

### Commonly Used Regexes (🆗🆗🆗)

Regexes are helpful for checking the validity of user input in JavaScript. One common type of input check is to validate whether it has any numeric characters. The following are five regexes that developers often use:

#### Any Numeric Characters: /\d+/ (🔢🔠)

   // Number console.log(/\d+/.test("123")) // true // Number and Letter console.log(/\d+/.test("33asd")) // true console.log(/\d+/.test("5asdasd")) // true // Only letter console.log(/\d+/.test("asdasd")) // false 

#### Only Alphanumeric Characters: /[a-zA-Z0-9] / (🔤🔤🔤)

   var regex = /[a-zA-Z0-9]/; // With Alphanumeric console.log(regex.test("somethingELSE")); // true console.log(regex.test("hello")); // true console.log(regex.test("112a")); // true console.log(regex.test("112")); // true // Without Alphanumeric console.log(regex.test("^")); // false 

#### Query String: /([^?=&]+)(=([^&]*))/ (🔎🔎🔎)

In web applications, web URLs pass parameters for routing or database query. For example, for the URL: http://your.domain/product.aspx?category=4& product_id=2140&query=lcd+tv, the URL might respond to a back-end SQL query like
the following:

SELECT LCD, TV FROM database WHERE Category = 4 AND Product_id=2140


To parse these parameters, regexes can be useful:

   var queryString = {}; 'http://your.domain/product.aspx?category=4&product_id=2140&query=lcd+tv'.replace( new RegExp ("([^?=&]+)(=([^&]*))?" , "g" ), function ($0,$1, $2,$3) { queryString[$1] =$3; } ); console.log('ID: ' + queryString['product_id' ]); // ID: 2140 console.log('Name: ' + queryString['product_name' ]); // Name: undefined console.log('Category: ' + queryString['category' ]); // Category: 4 

## Encoding (📄📄📄) Encoding is a general concept in computer science for transmission or storage. All computer file types are encoded in specific structures. For example, when you upload a PDF, the encoding may look like this:

1. JVBERi0xLjMKMSAwIG9iago8PCAvVHlwZSAvQ2F0YWxvZwovT3V0bGluZXMgMiAwIFIKL1Bh
Z2VzIDMgMCBS\
2. ID4+CmVuZG9iagoyIDAgb2JqCjw8IC9UeXBlIC9PdXRsaW5lcyAvQ291bnQgMCA+PgplbmR
vYmoKMyAwIG9i\
3. ago8PCAvVHlwZSAvUGFnZXMKL0tpZHMgWzYgMCBSCl0KL0NvdW50IDEKL1Jlc291cmNlcyA8
PAovUHJvY1Nl\
4. dCA0IDAgUgovRm9udCA8PCAKL0YxIDggMCBSCj4+
Cj4+Ci9NZWRpYUJveCBbMC4wMDAgMC4w
MDAgNjEyLjAw\
5. MCA3OTIuMDAwXQogPj4KZW5kb2JqCjQgMCBvYmoKWy9QREYgL1RleHQgXQplbmRvYmoKNSAw
IG9iago8PAov\
6. Q3JlYXRvciAoRE9NUERGKQovQ3JlYXRpb25EYXRlIChEOjIwMTUwNzIwMTMzMzIzKzAyJzAw
JykKL01vZERh\
7. dGUgKEQ6MjAxNTA3MjAxMzMzMjMrMDInMDAnKQo+PgplbmRvYmoKNiAwIG9iago8PCAvVHlw
ZSAvUGFnZQov\
8. UGFyZW50IDMgMCBSCi9Db250ZW50cyA3IDAgUgo+PgplbmRvYmoKNyAwIG9iago8PCAvRmls
dGVyIC9GbGF0\
9. ZURlY29kZQovTGVuZ3RoIDY2ID4+CnN0cmVhbQp4nOMy0DMwMFBAJovSuZxCFIxN9AwMzRTM
DS31DCxNFUJS\
10. FPTdDBWMgKIKIWkKCtEaIanFJZqxCiFeCq4hAO4PD0MKZW5kc3RyZWFtCmVuZG9iago4IDA
gb2JqCjw8IC9U\
11. eXBlIC9Gb250Ci9TdWJ0eXBlIC9UeXBlMQovTmFtZSAvRjEKL0Jhc2VGb250IC9UaW1lcy1
Cb2xkCi9FbmNv\
12. ZGluZyAvV2luQW5zaUVuY29kaW5nCj4+CmVuZG9iagp4cmVmCjAgOQowMDAwMDAwMDAwIDY
1NTM1IGYgCjAw\
13. MDAwMDAwMDggMDAwMDAgbiAKMDAwMDAwMDA3MyAwMDAwMCBuIAowMDAwMDAwMTE5IDAwMDA
wIG4gCjAwMDAw\
14. MDAyNzMgMDAwMDAgbiAKMDAwMDAwMDMwMiAwMDAwMCBuIAowMDAwMDAwNDE2IDAwMDAwIG4
gCjAwMDAwMDA0\
15. NzkgMDAwMDAgbiAKMDAwMDAwMDYxNiAwMDAwMCBuIAp0cmFpbGVyCjw8Ci9TaXplIDkKL1J
vb3QgMSAwIFIK\
16. L0luZm8gNSAwIFIKPj4Kc3RhcnR4cmVmCjcyNQolJUVPRgo=.....


This is a Base64-encoded PDF string . Data like this is often passed to the server when a PDF file is uploaded. (💡💡)

### Base64 Encoding (6️⃣4️⃣6️⃣4️⃣6️⃣4️⃣)

The .btoa() ( See on w3schools ) function creates a Base64-encoded ASCII string from a string. Each character in the string is treated as a byte ( 8 bits: eight 0 and 1 s).

The .atob() ( See on w3schools ) function decodes a string that has been encoded.

For example, the string “hello I love learning to computer program” in a Base64-encoded string looks like this:

aGVsbG8gSSBsb3ZlIGxlYXJuaW5nIHRvIGNvbXB
1dGVyIHByb2dyYW0


See my Glitch sample and click button below named (View App):

Note(📝): Click the script.js file and experiment with the code. (😊😊😊) Base64

In computer science, Base64 is a group of binary-to-text encoding schemes that represent binary data in an ASCII string format by translating it into a radix-64 representation. The term Base64 originates from a specific MIME content transfer encoding. Each non-final Base64 digit represents exactly 6 bits of data. Three 8-bit bytes can therefore be represented by four 6-bit Base64 digits.

## String Shortening (📐📏😝)

Have you ever wondered how URL-shortening sites such as Bit.ly work? A simplified URL compression algorithm follows a certain structure as shown here for www.google.com is an example:

1. The database creates a unique ID for the URL:
1. The ID is shortened into a string with Base62 encoding:

For the shortening part, there are 62 possible letters and numbers, consisting of 26 lowercase letters, 26 uppercase letters, and 10 numbers (0 to 9). The following algorithm can be used:

   var DICTIONARY = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".split(""); function encodeId(num) { var base = DICTIONARY.length; var encoded = ""; if (num === 0) { return DICTIONARY; } while (num > 0) { encoded += DICTIONARY[(num % base)]; num = Math.floor(num / base); } return reverseWord(encoded); } function reverseWord(str) { var reversed = ""; for (var i = str.length - 1; i >= 0; i--) { reversed += str.charAt(i); } return reversed; } function decodeId(id) { var base = DICTIONARY.length; var decoded = 0; for (var index = 0; index < id.split("").length; index++) { decoded = decoded * base + DICTIONARY. indexOf(id.charAt(index)); } return decoded; } console.log(encodeId(11231230)); // prints 'VhU2' console.log(decodeId('VhU2')); // prints '11231230' 

## Encryption (🔑🔒🔓) Have you ever seen the warning in Figure 4-3 in the Google Chrome browser (😐❓❓). This likely means the web site you are trying to access does not have the proper Secure Sockets Layer (SSL) certificate. TSL is a standard security for establishing an encrypted link between the server and the client. In this process, asymmetric encryption is used by the server. The browser only uses symmetric encryption :

1. The server sends its asymmetric public key to the browser.
2. The browser creates a symmetric key for the current session.
3. The server decrypts the browser’s session via its private key and retrieves the session key.
4. Both systems have the session key and will use this to transmit data securely.

This is secure because only the browser and the server know the session key. If the browser was to connect to the same server the next day, a new session key would be created.

The SSL warning message is a sign that the browser and server may not be encrypting the data on that connection. The most commonly used public-key encryption algorithm is the RSA algorithm.

## RSA Encryption (🔑🔑🔑)

RSA is an encryption algorithm based on factoring large integers. In RSA, two large prime numbers and a supplementary value are generated as public key. Anyone can use the public key to encrypt a message, but only those with the prime factors can decode the message. (💡💡💡)

There are three phases in the process: key generation, encryption, and decryption.

1. Key generation: The public key and private key are generated. The construction method of the keys
generated should be secret.

2. Encryption: The message can be encrypted via public key

3. Decryption: Only the private key can be used to decrypt the
message.

Here’s an overview of the algorithm:

1. Select two (usually large) prime numbers, $p$ and $q$ .
a. The product of $p$ and $q$ is denoted as $n$ .
b. The product of $\lparen p - 1 \rparen$ and $\lparen q - 1 \rparen$ is denoted as phi.
2. Choose two exponents, $e$ and $d$ .
a. $e$ is typically $3$ . Other values greater than $2$ can be used.
b. $d$ is a value such that $(e × d) \%\ phi = 1$ .

Encryption process is as shown:

m - message:
m^e % n = c
c - encrypted message


Decryption process is as shown:

c^d % n = m


This is the implementation of calculating $d$ :

   function modInverse(e, phi) { var m0 = phi, t, q; var x0 = 0, x1 = 1; if (phi == 1) return 0; while (e > 1) { // q is quotient q = Math.floor(e / phi); t = phi; // phi is remainder now, process same as // Euclid's algo phi = e % phi, e = t; t = x0; x0 = x1 - q * x0; x1 = t; } // Make x1 positive if (x1 < 0) x1 += m0; return x1; } modInverse(7, 40) // 23 

Key pairs of a public key and a private key also need to be generated. Let’s pick 5 and 11 as the primes:

   function modInverse(e, phi) { var m0 = phi, t, q; var x0 = 0, x1 = 1; if (phi == 1) return 0; while (e > 1) { // q is quotient q = Math.floor(e / phi); t = phi; // phi is remainder now, process same as // Euclid's algo phi = e % phi, e = t; t = x0; x0 = x1 - q * x0; x1 = t; } // Make x1 positive if (x1 < 0) x1 += m0; return x1; } function isPrime(n){ var prime_numbers=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] for(let i of prime_numbers){ if(n===i){ return true } } } function RSAKeyPair(p, q) { // Need to check that they are primes if (!(isPrime(p) && isPrime(q))) return; // Need to check that they're not the same if (p == q) return; var n = p * q, phi = (p - 1) * (q - 1), e = 3, d = modInverse(e, phi); // Public key: [e,n], Private key: [d,n] return [[e, n], [d, n]] } RSAKeyPair(5,11) //Public key: [3,55], Private key: [27,55] 

Let's use the secret message as number 2, higher than that will result to incorrect decryption. JavaScript internally uses floating point operation. If the numbers get big you should not be surprised if the answer is incorrect:

Encryption:

   // m - secret message: 2 // Always remember our secret message // m^e % n = c // 2^3 % 55 = 8 2**3 % 55 // You can also Math.pow(base,exponent) % modulus // Now the value is 8. Use the value of 8 to decryption 

Decryption:

   // c^d % n = m 8**27 % 55 // You can also use Math.pow(base,exponent) % modulus 

Complete: Encryption and Decryption

   function modInverse(e, phi) { var m0 = phi, t, q; var x0 = 0, x1 = 1; if (phi == 1) { return 0; } while (e > 1) { // q is quotient q = Math.floor(e / phi); t = phi; // phi is remainder now, process same as // Euclid's algo phi = e % phi // 3 % 40 e = t; // e = 40 t = x0; // t = 0 x0 = x1 - q * x0; // 1-0|13|3 x 0 x1 = t; // 0 } // Make x1 positive if (x1 < 0) { x1 += m0; } return x1; } function isPrime(n){ var prime_numbers=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] for(let i of prime_numbers){ if(n===i){ return true } } } function RSAKeyPair(p, q) { // Need to check that they are primes if (!(isPrime(p) && isPrime(q))) { return; } // Need to check that they're not the same if (p==q) { return; } var n = p * q, phi = (p-1)*(q-1), e = 3, d = modInverse(e,phi); // Public key: [e,n], Private key: [d,n] return [[e,n], [d,n]] } RSAKeyPair(5,11) for (let i in RSAKeyPair(5,11)){ var encrypted_message; const encryption=c=>{ var m=2,e=c,n=c,Encrypted_Message=m**e%n console.log("Encryption: "+Encrypted_Message) encrypted_message=Encrypted_Message } const decryption=c=>{ var d=c,n=c,Decrypted_Message=encrypted_message**d % n console.log("Decryption: "+Decrypted_Message) } i=="0"?encryption(RSAKeyPair(5,11)):i=="1"?decryption(RSAKeyPair(5,11)):false } 

This encrypts 2, and the receiver can decrypt that back to 2. The prime numbers chosen are very large for the RSA algorithm any higher than 2, if you wan to try, change the value of 2 at line 70 to 3 and you get different result.

This is because the prime factorization of large numbers takes time to compute. Today’s standard is 4,096-bit prime product. Figure 4-5 shows the largest possible value for a
4,096-bit number.

# Summary (📚)

In addition, a JavaScript Regex object can be used for string validation. Table 4-2 provides a summary:

# Up Next👉 Part 05: JavaScript Array 🔥 🔥 (July 07, 2020) Posted on by: ### Edison Pebojot(👨‍💻)

I started using computers and writing software around 2008 and 2009, I taught myself Programming. However, I wasn't a typical "nerd-klutz". 😅

### Discussion   