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

Learn Data Structure and Algorithm in JavaScript | Part 07

edisonnpebojot profile image Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป) Updated on ใƒป12 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, Part 04: JavaScript Strings, Part 05: JavaScript Array and Part 06: JavaScript Object

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. (๐Ÿ˜‰)
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 07: JavaScript Memory Management(๐Ÿ˜ฑ ๐Ÿ”ฅ ๐Ÿ’พ)

Alt Text

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. (๐Ÿ˜‰)

Memory Leaks (๐Ÿ’พ๐Ÿ’พ)

Alt text

A memory leak is a failure in a program causing impaired
performance
and even failure. Memory leaks can happen when garbage collectors (See on Wikipedia) do not free memory properly. Follow the key principles in this part to avoid memory leaks:

Reference to an Object (๐Ÿ“ฆโžก๏ธ๐Ÿ“ฆ)

In this example, say the memory() function returns 5KB of data:

Example:


var foo = {
    bar1: memory(), // 5kb
    bar2: memory() // 5kb
}

function clickEvent(){
    return foo.bar1[0]
}

clickEvent()

Enter fullscreen mode Exit fullscreen mode

Execution:

function memory() { return ['I am 10 kilobytes'] } var foo = { bar1: memory(), // 5kb bar2: memory() // 5kb } function clickEvent(){ return foo.bar1[0] } clickEvent()

You might expect the clickEvent() function to use 5KB of memory since it is only referencing bar1 from the foo object (๐Ÿ˜). The truth is (๐Ÿ˜Œ), it is using 10KB of memory since it has to load the whole foo object into the functionโ€™s scope to access the bar1 property. (๐Ÿ˜ƒ)

Leaking DOM (๐Ÿ’ฆ๐Ÿ‘Œ๐Ÿ‘ˆ)

If a variable pointing to a DOM element declared outside of an event callback, then it is in memory leaks if the element is deleted. In this example, there are two elements selected by document.getElementByID:

Example:


<div id="one">One</div>
<div id="two">Two</div>

Enter fullscreen mode Exit fullscreen mode

The following code in the Glitch sample below demonstrates the memory leak. When one is clicked, it removes two:

Note(๐Ÿ“): When one is clicked again, it still tries to reference the removed element, you can see it when the [object HTMLDivElement] still show multiple times. Click the view app and click one. Also, don't forget to see the script.js and index.html to see the idea how it works. (๐Ÿ‘)

The event listener will cause the two to disappear from the web. However, the reference to it will remain in event callback. This is a memory leak and should be avoided. (โš ๏ธ)

This can easily be fixed so that it wonโ€™t cause a memory leak, as shown here:

Example:


var one = document.getElementById("one");

one.addEventListener('click', function () {
    var two = document.getElementById("two");
    two.remove();
});

Enter fullscreen mode Exit fullscreen mode

Test it here:

Note(๐Ÿ“): If you fixed it, you can see the [object HTMLDivElement] is not showing multiple times, but only once, this is because we fixed the memory leak

Another way to address this is by unregistering the click handler once it has been used, as shown here:


var one = document.getElementById("one");
function callBackExample() {
    var two = document.getElementById("two");
    two.remove();
    one.removeEventListener("click", callBackExample);
}
one.addEventListener("click", callBackExample);


Enter fullscreen mode Exit fullscreen mode

Test it here:

Note(๐Ÿ“): If you fixed it, you can also see the [object HTMLDivElement] is not showing multiple times, but only once, this is because we fixed the memory leak by unregistering the click handler

Global window Object (๐ŸŒ๐Ÿ”๐Ÿ“ฆ)

If an object is on the global window object, it is in memory(meaning it is store in a memory). Any objects declared as a property of window will not be cleared. Remember that any global variable declared will be set as a property of the window object. In this example, there are one global variables declared:

Example:


var a = "apples"; //global variable

console.log(window.a); // prints "apples"

Enter fullscreen mode Exit fullscreen mode

Execution:

Note(๐Ÿ“): Click the view app and see the apples. Also, don't forget to see the script.js to see the idea how it works. (๐Ÿ‘)

Note(๐Ÿ“): It is good to avoid global variables whenever possible. This will help save memory. (๐Ÿ˜ƒ)

Limiting Object References (๐Ÿ“๐Ÿ“ฆโžก๏ธ)

An object is cleared when all references are cleared. Always remember to pull the property of an object instead of the entire object. This is because the objectโ€™s memory footprint can be very
large. If only one of the objectโ€™s properties is needed, you should avoid using the entire object as a parameter.

For example, do not do this(โš ๏ธ):

Example:


var test = {
    prop1: 'test'
}

function printProp1(test) {
    return test.prop1;
}

printProp1(test); // Prints 'test'

Enter fullscreen mode Exit fullscreen mode

Execution:

var test = { prop1: 'test' } function printProp1(test) { return test.prop1; } printProp1(test); // Prints 'test'

Instead, do this(pass the property like this)(๐ŸŒป):

Example:


var test = {
    prop1: 'test'
}

function printProp1(prop1) {
    return prop1;
}

printProp1(test.prop1); // Prints 'test'

Enter fullscreen mode Exit fullscreen mode

Execution:

var test = { prop1: 'test' } function printProp1(prop1) { return prop1; } printProp1(test.prop1); // Prints 'test'

The delete Operator (โŒโŒโŒ)

Always remember that the delete operator can be used to delete an unwanted object property (though it does not work on non-objects). Here's an example:

Example:


var test = {
    prop1: 'test'
}

console.log(test.prop1); // Prints 'test'

delete test.prop1;

console.log(test.prop1); // Prints 'undefined'

Enter fullscreen mode Exit fullscreen mode

Execution:

var test = { prop1: 'test' } console.log(test.prop1); // Prints 'test' delete test.prop1; console.log(test.prop1); // Prints 'undefined'

Summary (๐Ÿ“š)

Alt text

Although memory in JavaScript is not allocated by the programmer, there are still ways to mitigate memory leaks. If the object is in reference, it is in memory(meaning it is store in the memory). Similarly, DOM elements should not be referenced once deleted. In many cases, it is more applicable to pass a property of the object rather than the object itself. Also, be extremely mindful when declaring a global variable.

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

Alt text

In this part, challenges are about identifying memory inefficiencies and optimizing a given piece of code. Have some time to solve this riddle while waiting for part 8. Just make sure to share your solution in the comment: (๐Ÿ˜ƒ)


ANALYZING AND OPTIMIZING A PROPERTY CALL

Problem: An excessive amount of memory is used in printProperty because the entire object is brought into the printProperty function. To fix this, only the property being printed should be brought in as a parameter of the function. Analyze and optimize the call for printProperty:

Sample:


function someLargeArray() {
    return new Array(1000000);
}
var exampleObject = {
    'prop1': someLargeArray(),
    'prop2': someLargeArray()
}
function printProperty(obj) {
    console.log(obj['prop1']);
}
printProperty(exampleObject);

Enter fullscreen mode Exit fullscreen mode

Answer: (Remember to put your answer in the comment)


ANALYZING AND OPTIMIZING SCOPE

Problem: Global variables are used where not necessary. Albeit(although.) small, the global variables RED, GREEN, and BLUE bloat the global scope and should be moved inside the redGreenBlueCount function. Analyze and optimize the global scope for the following code block:

Sample:


var RED = 0,
    GREEN = 1,
    BLUE = 2;
function redGreenBlueCount(arr) {
    var counter = new Array(3).fill(0);
    for (var i = 0; i < arr.length; i++) {
        var curr = arr[i];
        if (curr == RED) {
            counter[RED]++;
        } else if (curr == GREEN) {
            counter[GREEN]++;
        } else if (curr == BLUE) {
            counter[BLUE]++;
        }

    }
    return counter;
}
redGreenBlueCount([0, 1, 1, 1, 2, 2, 2]); // [1, 3, 3]

Enter fullscreen mode Exit fullscreen mode

Answer: (Remember to put your answer in the comment)


ANALYZING AND REPAIRING MEMORY ISSUES

Problem: This is the leaking DOM issue discussed earlier in the part. When elements are removed, they are still referenced by the callback function. To address this, put the one and two variables into a callbackโ€™s scope and remove the event listener after. Analyze and fix memory issues for the following code:

Sample HTML:

<button id="one">Button 1</button>
<button id="two">Button 2</button>
Enter fullscreen mode Exit fullscreen mode

Sample JavaScript:


var one = document.querySelector("#one");
var two = document.querySelector("#two");
function callBackExample() {
    one.removeEventListener("", callBackExample);
}
one.addEventListener('hover', function () {
    two.remove();
    console.log(two); // will print the html even after deletion
});
two.addEventListener('hover', function () {
    one.remove();
    console.log(one); // will print the html even after deletion
});

Enter fullscreen mode Exit fullscreen mode

Note(๐Ÿ“): Make sure by answering is to use glitch

Answer: (Remember to put your answer in the comment)


Up Next๐Ÿ‘‰ Part 08: Recursion (๐Ÿ”ฅ๐Ÿ”ฅ) (July 16-17, 2020)


Alt text

Posted on by:

edisonnpebojot profile

Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป)

@edisonnpebojot

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

Discussion

pic
Editor guide