loading...
Cover image for Learn Data Structure and Algorithm in JavaScript | Part 05

Learn Data Structure and Algorithm in JavaScript | Part 05

edisonnpebojot profile image Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป) Updated on ใƒป17 min read


Prerequisite (โœ‹๐Ÿ˜)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers, and Part 04: JavaScript Strings

Part Table of Contents Description
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. (๐Ÿ˜‰)

Part 05: JavaScript Arrays(๐Ÿ˜ฑ ๐Ÿ”ฅ ๐Ÿ“Š)

Alt Text

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 (๐Ÿ’ช)

Introducing Arrays (๐Ÿ“Š)

Alt text

Arrays are one of the most fundamental data structures. If you have ever programmed before, youโ€™ve most likely used an array. (๐Ÿ˜Œ)

var array = [1,2,3,4]

For any data structure, developers are interested in time and space complexity with the four fundamental operations: access, insertion, deletion, and search.

Insertion (๐Ÿ–๐Ÿ‘ˆ๐Ÿ‘ˆ)

Insertion means adding a new element. JavaScript array insertion .push( element ) method adds a new element at
the end of the array:

var array = [1, 2, 3, 4]; array.push(5) //array = [1,2,3,4,5] array.push(7) //array = [1,2,3,4,5,7] array.push(2) //array = [1,2,3,4,5,7,2] array

The time complexity of this operation is O(1))O \lparen 1 \rparen) in theory. Practically, this depends on the JavaScript engine that runs the code of course. (๐Ÿ˜‰)

Another way to add an element is unshift() method. This
method will add at the first index in the array:

var array = [1, 2, 3, 4]; array.unshift(5) //array = [5,1,2,3,4] array.unshift(7) //array = [7,5,1,2,3,4] array.unshift(2) //array = [2,7,5,1,2,3,4] array

Deletion (โŒโŒโŒ)

JavaScript array deletion .pop() method removes the
last element of the array. This also returns the removed element:

var array = [1, 2, 3, 4]; console.log(array.pop()) //returns 4, array = [1,2,3] //console.log(array.pop()) //returns 3, array = [1,2] // Uncomment this array

The time complexity of .pop is O(1)O \lparen 1 \rparen

Another way to remove an element is .shift() method. This
method will remove the first element and return it:

var array = [1,2,3,4]; console.log(array.shift()) //returns 1, array = [2,3,4] //console.log(array.shift()) //returns 2, array = [3,4] // Uncomment this array

Access (๐Ÿ”‘๐Ÿ”‘๐Ÿ”‘)

Accessing an array at a specified index only takes O(1)O \lparen 1 \rparen because this process get the value directly from the memory:

var array = [1,2,3,4]; console.log(array[0]) //returns 1 console.log(array[1]) //returns 2

Iteration (๐ŸŒ€๐ŸŒ€๐ŸŒ€)

Iteration is the process of accessing each of the items. There are ways to iterate through an array. They all have a time
complexity of O(n)O \lparen n \rparen since the iteration is visiting nn (or the number of elements).

for (Variables; Condition; Modification) (4๏ธโƒฃ๐ŸŒ€๐ŸŒ€)

for is the most common method of iteration. It is most often used in this form:

//var array=[1,2,3,4,5] // Remove the '//' before var array for (var i = 0, len = array.length; i < len; i++) { console.log(array[i]); }

The previous code simply means initialize the variable i, check whether the condition is false (i<len), and then modify (i++) until the condition is false.

You can implement an infinite loop using a for loop by not setting a condition, as shown here:

for (; ;) { console.log('I am infinite!') }

for (in) (1๏ธโƒฃ2๏ธโƒฃ3๏ธโƒฃ4๏ธโƒฃ)

Another way to iterate is to call the indices(index) one by one. The variable index is the index of the array, as follows:

var array = ['all', 'cows', 'are', 'big']; for (var index in array) { console.log(index); } // This prints the following: '0,1,2,3'

To print the values, use this:

var array = ['You', 'are', 'pig']; for (var index in array) { console.log(array[index]); } // This prints 'You are pig'

for (of) (๐Ÿ…ฐ๏ธ๐Ÿ…ฑ๏ธ๐Ÿ…ฐ๏ธ)

The variable element is the value of the array, as follows:

var array = ['If', 'am', 'bad', 'then', 'I', 'am', 'your', 'dad']; for (var element of array) { console.log(element); } // This prints ' If am bad then I am your dad' :)

forEach( ) (๐Ÿพ๐Ÿพ๐Ÿพ)

The difference between forEach and other iteration is that forEach cannot break the iteration or skip elements in the array. forEach is more expressive (๐Ÿ˜˜):

var array = ['With', 'great', 'power', 'comes', 'with', 'great', 'electricity', 'bill']; array.forEach((element, index)=>console.log(element)) // Remove the '//' //array.forEach((element, index)=>console.log(array[index])) // This prints 'With great power comes with great electricity bill'

Helper Functions (๐Ÿ‘ฌ๐Ÿ‘ฌ๐Ÿ‘ฌ)

Alt text

.slice(begin,end) (๐Ÿ”ชโœ‚๏ธ๐Ÿ“ฐ)

This helper function returns a portion of an array without modifying the array. .slice() takes two parameters: the beginning index and the ending index of the array:

var array = [1, 2, 3, 4]; console.log(array.slice(1, 2)) //returns [2], array = [1,2,3,4] console.log(array.slice(2, 4)) //returns [3,4], array = [1,2,3,4]

If only the beginning index is passed, the ending index will assumed to be the maximum index(๐Ÿ”š):

var array = [1, 2, 3, 4]; console.log(array.slice(1)) //returns [2,3,4], array = [1,2,3,4] console.log(array.slice(1,4)) //returns [2,3,4], array = [1,2,3,4]

If nothing is passed, this function simply returns a copy of the array:

var array = [1, 2, 3, 4] console.log(array.slice()) //returns [1,2,3,4], array = [1,2,3,4]

It should be noted that array.slice() === array evaluates to false. This is because the memory address those arrays differently.

slice() is useful for copying an array. Remember that arrays in JavaScript are reference-based(connected), meaning that if you assign a new variable to an array, changes to that variable apply to the original array:

var array_one = [1, 2, 3, 4],array_two = array_one // Before: // array_one = [1,2,3,4] // array_two = [1,2,3,4] // After: array_two[0] = 5; console.log(array_one) // array_one [5,2,3,4] console.log(array_two) // array_two [5,2,3,4]

The changing element changed by accident because it is
a reference to the original array. To create a new array, you can use Array.from( new array ):

var array_one = [1, 2, 3, 4],array_two = Array.from(array_one) // Before: // array_one = [1,2,3,4] // array_two = [1,2,3,4] // After: array_two[0] = 5; console.log(array_one) // array_one [1,2,3,4] console.log(array_two) // array_two [5,2,3,4]

Array.from() takes O(n)O\lparen n \rparen , where nn is the size of the array. This is automatic because copying the array requires copying all nn elements of the array.

.splice(begin,size,element1,element2โ€ฆ) (1๏ธโƒฃ๐Ÿ“๐Ÿ“„)

This helper function changes the contents of an array by removing and/or adding new elements. .splice() takes three parameters: the beginning index, size to be removed, and the new elements to add.

New elements are added at the position specified by the first parameter. It also returns the removed elements:

var array = [1, 2, 3, 4]; // Before: array = [1,2,3,4] // After: return [], array=[1,2,3,4] console.log(array.splice()) // Before: array = [1,2,3,4] // After: return [2,3], array=[1,4] console.log(array.splice(1, 2))

Object type can be also added to the array:

var array = [1, 2, 3, 4]; console.log(array.splice(1, 2, [5, 6, 7])) //returns [2,3], array = [1,[5,6,7],4] array = [1, 2, 3, 4]; console.log(array.splice(1, 2, { 'ss': 1 })) //returns [2,3], array = [1,{'ss':1},4]

.splice() is O(n)O \lparen n \rparen

Similarly to copying, if the range of .splice( ...range ) method specified is the whole array, then each nn item from that array has to be removed.

Concat (โœ‚๏ธโž•๐Ÿ“ƒ)

Concat() adds new elements to the array at the end of the array and returns the results array:

Note(๐Ÿ“): Concat() don't change the original array, but instead copy the original array to a new array

var array = [1, 2, 3, 4] console.log(array.concat()) //returns [1,2,3,4], array = [1,2,3,4] console.log(array.concat([2, 3, 4])) //returns [1,2,3,4,2,3,4], array = [1,2,3,4]

.length Property (๐Ÿ“๐Ÿ“๐Ÿ“)

The .length property returns the size of the array:

var array = [1, 2, 3, 4]; array.length //prints 4

But changing this property to a lower size can delete elements from the array:

var array = [1, 2, 3, 4] console.log("Original Array:"+array.length) //prints 4 array.length = 3 "New Array:"+array.length // prints '3'

Spread Operator (๐ŸŽ‰๐ŸŽ‰๐ŸŽ‰)

The spread operator (...) is used to expand arguments(or values):

var sum=(a, b, c, d)=>a + b + c + d var numbers = [1, 2, 3, 4]; sum(...numbers); // prints '10'

Both the Math.max and Math.min functions can use the spread operator. To find the maximum in an array, use this:

var array = [1,2,3,4,5]; Math.max(...array) // print '5'

To find the minimum in an array, use this:

var array = [3,2,-123,2132,12]; Math.min(...array) // print '-123'

JavaScript Functional Array Methods (๐Ÿพ๐Ÿพ๐Ÿพ)

Alt text

JavaScript can be written like a functional programming language. It does not use loops (๐Ÿ˜), only function (method) calls (๐Ÿ˜Š).

In this section, only three functional array methods in JavaScript will be explored (๐Ÿ˜ญ): map, filter, and reduce.

Note(๐Ÿ“): These methods do not change the original array contents

Map (๐Ÿ“œ๐Ÿ“Œ๐Ÿšฉ)

The map function transform every element in the array
and returns a new array. For example, you can multiply every element by 10, as shown here:

[1, 2, 3, 4, 5, 6, 7].map(value=>value * 10) // prints '[10, 20, 30, 40, 50, 60, 70]'

Filter (๐Ÿšฏ๐Ÿ“ต๐Ÿšณ)

The filter function returns only elements that meet condition. For example, this filters elements greater than 100:

Note(๐Ÿ“):Again, this does not change the original array. (๐Ÿ˜‘)

[100, 2003, 10, 203, 333, 12].filter(value=>value > 100) // prints '[2003, 203, 333]'

Reduce (๐Ÿ“‰๐Ÿ“‰๐Ÿ“‰)

The reduce function combines all the elements into one value. For example, this adds all the elements:

[0, 1, 2, 3, 4].reduce((prevVal, currentVal, index, array)=>prevVal + currentVal) // prints '10'

This function also can take its second argument (๐Ÿ˜ฑ). For example, providing 1 will yield to 11, as shown here:

[0, 1, 2, 3, 4].reduce((prevVal, currentVal, index, array)=>prevVal + currentVal,1) // prints '10'

Multidimensional Arrays (๐ŸŒ’๐ŸŒ˜๐ŸŒ‘)

A multi-dimensional array is an array with a degree or dimension greater than one. For example, a 2D array, or two-dimensional array, is an array of arrays, meaning rows and column matrix

Alt text

JavaScript doesn't natively provide the multidimensional array like the one below:

Alt Text

Figure 5-1. Multidimensional array

See Figure 5-1, unlike Java and C++, JavaScript does not have multidimensional arrays. (๐Ÿ˜ฟ)

Alt Text

Figure 5-2. Jagged array

Instead, there are jagged arrays ! (๐Ÿ˜น) at the Figure 5-2. A jagged array is an array whose elements are arrays.

Alt Text

Figure 5-3. Three-by-three matrix

Here is a function to create a jagged array like the one in Figure 5-3:

function Matrix(rows, columns) { var jaggedarray = new Array(rows); for (var i = 0; i < columns; i += 1) { jaggedarray[i] = new Array(rows); } return jaggedarray; } Matrix(3, 3)

By defining an array of elements, you can create a multidimensional array, where each element is another array too. For this reason we can say a multidimensional array of JavaScript is an array of arrays.

Alt Text

Figure 5-4. Three-by-three matrix of numbers

To access elements in a jagged array, specify a row and a column (see Figure 5-4):

var matrix3by3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]; /* Access column */ console.log("Column 1:"+matrix3by3[0]) // [1,2,3] console.log("Column 2:"+matrix3by3[1]) // [4,5,6] console.log("Column 3:"+matrix3by3[2]) // [7,8,9] /* Access row 1, 2 and 3 in column 1 */ console.log("Column 1 Row 1:"+matrix3by3[0][0]) // 1 console.log("Column 1 Row 2:"+matrix3by3[0][1]) // 2 console.log("Column 1 Row 3:"+matrix3by3[0][2]) // 3 /* Access row 1, 2 and 3 in column 2 */ console.log("Column 2 Row 1:"+matrix3by3[1][0]) // 4 console.log("Column 2 Row 2:"+matrix3by3[1][1]) // 5 console.log("Column 2 Row 3:"+matrix3by3[1][2]) // 6 /* Access row 1, 2 and 3 in column 3 */ console.log("Column 3 Row 1:"+matrix3by3[2][0]) // 7 console.log("Column 3 Row 2:"+matrix3by3[2][1]) // 8 console.log("Column 3 Row 3:"+matrix3by3[2][2]) // 9

Summary (๐Ÿ“š)

Alt text
Various array functions were covered in this part and are
summarized in Table 5-1

Function Usage
push(element) Adds an element to the end of the array
pop() Removes the last element of the array
shift() Removes the first element of the array
slice(beginIndex, endIndex) Returns a part of the array from beginIndex to endIndex
splice(beginIndex, endIndex) Returns a part of the array from beginIndex to endIndex and modifies the original array by removing those elements
concat(arr) Adds new elements (from arr) into the array at the end of array
Table 5-1. Array Function Summary

An iteration of array elements can use the loop mechanisms shown in Table 5-2:

Function Usage
for (var prop in arr) Iterates by the index of the array element
for (var elem of arr) Iterates by the value of the array element
Table 5-2. Iteration Summary

Finally, recall that JavaScript utilizes jagged arrays, an array of arrays, to get multidimensional array. (๐Ÿ˜Š)

Challenge (๐Ÿ˜ค๐Ÿ”ฅ๐Ÿ‘Š)

Alt text

Have some time to solve this riddle while waiting for part 6. However, there is sample code and explanation, solve this on your own, and have your own code other than the code and explanation provided below, I don't want to see your answer or explanation (or if you want to show it all right, just make sure to share it in the comment: (๐Ÿ˜…)


FIND TWO ARRAY ELEMENTS IN AN ARRAY THAT ADD UP TO A NUMBER

Problem: Given the array arr, find and return two indices of the array that add up to weight or return -1 if there is no combination that adds up to weight

Explanation: For example, in an array like [1,2,3,4,5], what numbers add up to 9?


FIND THE MEDIAN OF TWO SORTED ARRAYS OF THE SAME SIZE

Problem: Recall that median in an even number of a set is the average of the two middle numbers. If the array is sorted, this is simple.

Explanation: [1,2,3,4] has the median of (2+3)/2 = 2.5


FIND COMMON ELEMENTS IN K-SORTED ARRAYS

Alt Text

Figure 5-4. Three Variables

Problem: In this example with three arrays, k=3.

Exaplanation: To do this, simply iterate over each array and count instances of every element. However, do not track repeated ones (5 and 5.5 should be counted once in one array iteration). To do this, check whether the last element is the same before incrementing. This will work only if it is sorted.


SPIRAL PRINT

Alt Text

Figure 5-5. Spiral Print

Problem: Letโ€™s create an example problem with a matrix. Given a matrix, print the elements in a spiral
order, like in Figure 5-5.

Explanation: This looks like a daunting task at first. However, the problem can be broken down to five main
components. Printing from left to right, printing from top to bottom, printing from right to left, printing from bottom to top, keeping a limit on these four operations


Up Next๐Ÿ‘‰ Part 06: JavaScript Object ๐Ÿ”ฅ ๐Ÿ”ฅ (July 08-09, 2020)


Alt text

Discussion

markdown guide