Forem: Chuck Choi

Data Structure Series: Hash Table

Chuck Choi — Mon, 16 Aug 2021 22:28:31 +0000

Introduction

We use forks to eat pasta, spoons to eat soup, and chopsticks to eat dumplings. Each silverwares have its advantages/disadvantages, hence working better than the other for the food that it interacts well with. Just like that, different data structures are better suited and perform better than the others based on the situations/use cases. They each have their pros and cons. Understanding these pros and cons can help you be a better programmer, as it will allow you to choose an appropriate data structure(s) based on the circumstances/goals you have, and it helps to drastically improve the performance of the algorithm being applied. I will be putting these blog series together on well known programming data structures in JavaScript, and link them all in one blog post in the future. Feel free to leave a comment if you have any questions!

1. What Is Hash Table?
2. Hash Function
3. Implementation in JavaScript
4. Helper Functions
5. Handling Collisions
6. Big O
7. Helpful Resources

1. What is Hash Table?

Hash Table is a data structure of associative array that stores key/value paired data into buckets.

Considered being one of the most important data structures in computing, Hash Table is used in many areas of applications: password verifications, cryptography, compilers, and the list goes on. Due to its efficiency and speed in searching, insertion, and removal of data, it is a widely applicable and preferred data structure in many cases. A Hash Table is a data structure of associative array that stores data as a key/value pair into a bucket.

How Hash Table works is that it takes a key and a value as inputs, then runs the key through a hash function that turns it into an index. This process is called hashing. The index is used to map the value of the input into the table's bucket. The hash function is irreversible, which makes it secure and reliable. It is possible for two different keys to result in the same index though, and this is called a collision. A collision can override the previous key's placeholder if not handled. There are various ways to handle hash collisions though -- Separate Chaining being one of them which often uses Linked Lists inside the bucket to store multiple data in the same index. We will get into it later in this post. But first, let's discuss how hash function works in a nutshell.

2. Hash Function

The hashing process in computing is like hashing a potato to make hashed brown.

Hash functions, or hashing algorithms generate a fixed-length result from a given input. This process is called hashing. The fixed-length result is used in Hash Tables as an index to map the input into a hash bucket. The hashing process in computing is like hashing a potato to make hashed brown. You could think of potato as key input, grater as hash function, and shredded potato as index that is hashed out as a result of the hash function. Just like how you can't turn shredded potato back into a whole potato, hash functions are irreversible -- it's a one way algorithm.

Here is an example of a hash function in JavaScript:

function hash (key, size) {
    let hashedKey = 0;
    for (let i = 0; i < key.length; i++) {
        hashedKey += key.charCodeAt(i)
    }
    return hashedKey % size
}

Pseudocode:

This function accepts two arguments: string key to hash, and size of hash buckets
Initialize a variable named hashedKey as 0 to return at the end
Iterate each of the string's characters to sum up their character codes
After the iteration, use modulo operation (%) to find the remainder of the hashedKey / size and set it as new hashedKey
Return hashedKey

Explanation
In the above algorithm, we are initializing a variable hashedKey as 0. The value of this variable will change based on the string and be returned as a result of this function. We need a way to represent each of the letters into numbers, this way the matching string key that goes through the function will always convert to the same integer. JavaScript's string method charCodeAt() allows us to convert a string character into an integer representing the UTF-16 code unit.

With that being said, we are using a for loop to iterate every character of the key input. For each character being iterated, we are using the charCodeAt() method to convert the character and add it to hashedKey variable we defined at the beginning. Once we sum up all the integers that represents each characters, we execute an modulo operation % using the size of the bucket (second argument of the function) as a divisor. Modulo operation not only guarantees that the resulting integer is in range between 0 to the size of the bucket, but also makes the result irreversible.

This is a very simple and basic hash function that can be improved better. I recommend you to check out this blog post if you are interested in learning about different hash functions designed by mathematicians and computer scientists around the world. Now it is time to implement the hash table in JavaScript!

3. Implementation in JavaScript

class HashTable {
    constructor(size=53) {
        this.size = size
        this.buckets = new Array(size);
    }
    _hash (key) {
        let hashedKey = 0;
        for (let i = 0; i < key.length; i++) {
            hashedKey += key.charCodeAt(i)
        }
        return hashedKey % this.size
    }
}

let table = new HashTable()

console.log(table) // HashTable {size: 53, buckets: Array(53)}

The above Hash Table class has two properties:

size: the number representing the size of the buckets, and we are using prime number 53 as a default value (choosing a prime number for the hash table's size reduces the chances of collisions)
buckets: buckets are the placeholders for each data (key/value pair), and we are using Array class to create an empty array with size of 53 indices

And we have the _hash method similar to what we created earlier, but only difference is that it is not taking in the size as second argument since we are using the size of the object created from the Hash Table class. With this, we can create an object with buckets array that contains default size of 53 indices or a specified size.

Let's go ahead and add some methods to this Hash Table!

4. Helper Functions

set()

// adds key-value pair into hash table's bucket
set(key, value) {
    let index = this._hash(key)
    this.buckets[index] = [key, value];
}

Pseudocode:

Accepts a key and a value
Hashes the key
Stores the key-value pair in the hash bucket

get()

// retrieves the value of the key from its respective bucket
get(key) {
    let index = this._hash(key)
    return this.buckets[index][1] // returns value of the key
}

Pseudocode:

Accepts a key
Hashes the key
Retrieves the key-value pair in the hash bucket

remove()

// removes the key-value pair from the hash table's bucket
remove(key) {
    let index = this._hash(key)
    let deleted = this.buckets[index]
    delete this.buckets[index]
    return deleted
}

Pseudocode:

Accepts a key
Hashes the key
Retrieves the key-value pair in the hash bucket and stores it
Delete the key-value pair in the hash bucket (use delete operator to empty the element, doesn't affect the array size)
Returns the stored key-value pair

All the helper functions in this data structure is fairly simple -- they all utilize the hash function we defined earlier to retrieve the index that is associated with the key passed, and access the array's element in that index. There's a problem with these methods though. What happens if the hash function returns the same index for two different inputs? Our hash function is fairly simple so this will happen for sure. If so, it will override the bucket that is already occupied or get method will retrieve a wrong value that we aren't looking for. How can we improve these helper methods to handle the collisions?

5. Handling Collisions

As we discussed earlier, it is possible for a hash function to produce collisions: returning the same index for multiple different keys. Unfortunately, even under the best of circumstances, collisions are nearly unavoidable. Any hash function with more inputs than outputs will necessarily have such collisions; the harder they are to find, the more secure the hash function is.

There are multiple ways to handle collisions though, and the two common techniques are Separate Chaining and Linear Probing.

Separate Chaining: If there is only one hash code pointing to an index of array then the value is directly stored in that index. If hash code of second value also points to the same index though, then we replace that index value with a linked list or array and all values pointing to that index are stored in the list. Same logic is applied while retrieving the values, we will have to iterate all the elements inside a bucket if the bucket stores multiple key-value pairs. In short, separate chaining creates a list-like object inside a bucket to store multiple data with collisions.

Linear Probing: Linear Probing technique works on the concept of keep incrementing the hashed index until you find an empty bucket. Thus, Linear Probing takes less space than Separate Chaining , and perform significantly faster than Separate Chaining (since we don't have to loop through lists inside buckets).

Although Separate Chaining is significantly less efficient than Linear Probing, it is easier to implement. Here's how we can improve the helper methods we defined by utilizing Separate Chaining (we will use Array instead of Linked List for simplicity):

set()

// adds key-value pair into hash table's bucket
set(key, value) {
    let index = this._hash(key)
    if(!this.buckets[index]) {
        this.buckets[index] = [];
    }
    this.buckets[index].push([key, value]);
}

Pseudocode:

Accepts a key and a value
Hashes the key
If the hash bucket is empty, set it as an empty array
Push the key-value pair in the array inside the bucket

get()

// retrieves the value of the key from its respective bucket
get(key) {
    let index = this._hash(key)
    if(this.buckets[index]) {
        for(let i = 0; i < this.buckets[index].length; i++) {
            if(this.buckets[index][i][0] === key) {
                return this.buckets[index][i][1]
            }
        }
    }
    return undefined
}

Pseudocode:

Accepts a key
Hashes the key
If the bucket is truthy, iterate each key-value pair inside the bucket
If the key matches the pair, return the value of the pair
return undefined if the bucket is empty

remove()

// removes the key-value pair from the hash table's bucket
remove(key) {
    let index = this._hash(key)
    if(this.buckets[index]) {
        for(let i = 0; i < this.buckets[index].length; i++) {
            if(this.buckets[index][i][0] === key) {
                return this.buckets[index].splice(i, 1)
            }
        }
    }
}

Pseudocode:

Accepts a key
Hashes the key
If the bucket is truthy, iterate each key-value pair inside the bucket
If the key matches the pair, remove the pair and return it

6. Big O

Space Complexity:
- O(n)
- Space complexity of this data structure is linear: as the size of the buckets increase, so does the space
Set/Get/Remove:
- Average: O(1) Time Complexity
- Worst Case: O(n) Time Complexity
- All these helper methods use hash function to look up the indices. Hash function takes constant time, but the time complexity can get linear with buckets with multiple elements due to collisions. More items will mean more time to look inside the bucket, hence taking linear time (O(n))

7. Helpful Resources

Online Course (Udemy Course)
Check out this Udemy course named JavaScript Algorithms and Data Structures Masterclass! It is created by Colt Steele, and I referenced his code for the data structure implementation part of this blog post. Personally, I didn't know where to start with algorithms and data structures especially coming from a non-tech background. This course is very well structured for beginners to build a foundation on these topics.

Visual Animation (VisuAlgo)
Data structures can be difficult to comprehend for some people just by looking at the code/text. The instructor in the course above uses a website named VisuAlgo that has visual representation of algorithms and data structures through animation.

Data Structure Cheat Sheet (Interview Cake)
Also, here's a really well-summarized cheat sheet/visualizations on data structures.

CS50's Hash Tables Lesson (YouTube Video)
I came across this YouTube video thanks to one of the DEV Community users Alex @tinydev! It's part of Harvard's CS50 course, and they do a great job explaining Hash Tables.

Data Structure Series: Stack & Queue

Chuck Choi — Wed, 11 Aug 2021 14:39:26 +0000

Introduction

We use forks to eat pasta, spoons to eat soup, and chopsticks to eat dumplings. Each silverwares have its advantages/disadvantages, hence working better than the other for the food that it interacts well with. Just like that, different data structures are better suited and perform better than the others based on the situations/use cases. They each have their pros and cons. Understanding these pros and cons can help you be a better programmer, as it will allow you to choose an appropriate data structure(s) based on the circumstances/goals you have, and it helps to drastically improve the performance of the algorithm being applied. Feel free to leave a comment if you have any questions!

1. What are Stacks and Queues?
2. Implementation in JavaScript
3. Implementation Using Linked List
4. Big O
5. Helpful Resources

1. What are Stacks and Queues?

Stacks and Queues are two types of linear data structures with a main difference in their data management principle: LIFO (Last-In, First-Out) for Stacks, and FIFO (First-In, First-Out) for Queues.

Stack

A Stack is a linear data structure that follows LIFO (Last-In, First-Out) principle. With LIFO principle, whatever the data came in last would be the first to be taken out. An example you'd be familiar with would be the Undo functionality in a text editor like Word Processor. In a Word document, the Undo command undoes any last action you do, which includes formatting text, moving blocks, typing and deleting text, formatting, and etc. Using the Undo command until the end will eventually take you to a blank page where you started like a Stack.

I remember I used to play with this plastic toy named "Rock-A-Stack". This toy comes with with a base with a center cone on top, and multiple colorful plastic rings in different sizes. Your goal is to stack the rings on top of the base in the order of the size from biggest to smallest to form a pyramid shape. The ring cannot be taken out from the bottom because of the base, you will have to take out the whatever the ring is at the topmost position of the stack in order to re-arrange the order. A Stack in the programming world is fundamentally no different than the toy Rock-A-Stack.

Queue

A Queue is also a linear data structure, but follows FIFO (First-In, First-Out) principle. With FIFO principle, whatever the data came in first would be the first to be taken out. A printer queue is a good example of a Queue data structure. In an office setting where one or few printers are shared by multiple people, queue makes sure that the printing tasks are executed in the chronological order they came in. Even if you were to use a printer at home and print multiple instances of document pages, it pushes the tasks in a queue. Let's say you forgot to turn on the printer, the queue will make sure that the printing tasks are not lost, but will execute each tasks as a queue so that first printing task will be executed first once the printer is turned on.

A real life example would be a security scanning line at the TSA, or any other lines like at an amusement park, restaurant, and etc. Nobody likes it when someone cuts the line. You have to wait until your turn comes. If you are the first one to arrive at the TSA line, you will go through the security scanning first. That's a Queue right there, First-In, First-Out.

In Summary, Stacks and Queues are two types of linear data structures with a main difference in their data management principle: LIFO (Last-In, First-Out) for Stacks, and FIFO (First-In, First-Out) for Queues.

2. Implementation Using Array

Stacks and Queues can simply be implemented using a built in Array in JavaScript. For Stacks, you just need to use Array's push() and pop() methods to add and element at the end of an array, and remove the element at the end. For Queues, you will have to use push() method to add an element at the end, but use shift() to take out the first element that was pushed in. They will look something like this:

Stack

const stack = [];
stack.push('Baseball')
stack.push('Soccer')
stack.push('Football')
stack.push('Basketball')

return stack // ["Baseball", "Soccer", "Football", "Basketball"]

stack.pop() // returns "Basketball"

return stack // ["Baseball", "Soccer", "Football"]

Queue

const queue= [];
queue.push('Peanut Butter')
queue.push('Milk')
queue.push('Apple')
queue.push('Cheese')

return queue // ["Peanut Butter", "Milk", "Apple", "Cheese"]

queue.shift() // returns "Peanut Butter"

return queue // ["Milk", "Apple", "Cheese"]

This is totally easy and convenient for Stacks. But there is a downside of implementing a Queue using Array. Can you guess what it is? push() and pop() methods have time complexity of O(1) while shift() and unshift() methods have time complexity of O(N). This is because when you are adding or removing an element of an array, all the elements to the right side of that element has to rearrange their position, thus indices of those get reassigned.

Since shift() and unshift() are pretty costly in Array, let's see if there's a way to optimize Stacks and Queues. Aha! Linked Lists are great at inserting/deleting the first and the last element! If you remember how Linked List works, a Linked List is a collection of data in a sequence, with each of the data referencing its next node (or previous node if it is a Doubly Linked List) from its head to the tail. For us to visualize it better using Stacks & Queues, we will call the pointers first and last instead of head and tail.

Singly Linked Lists' nodes reference their next node but not their previous. Adding a new first node to a Singly Linked List is quick, we just need to replace the new first, and set its next node to the old first node. Removing the current first node is quick as well, we just need to remove the current first node, and set its next node as the new first node. This makes Singly Linked List a perfect candidate for Stacks to follow LIFO (Last-In, First-Out) principle. However, if we were to add a new node to a queue (enqueue) and remove the last node (dequeue) using Singly Linked List, it will not be efficient to dequeue the last node. This is because a Singly Linked List's node does not reference its previous node, so we will have to traverse the entire list to find out what the previous node of last node is. The previous node of last node will need to be reassigned as the new last node. Thus, a Queue will be more optimized to utilize Doubly Linked List over Singly Linked List. Check out the code below:

3. Implementation Using Linked List

Stack

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}
class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    // push() method adds a new node at the top (first)
    push(value){
        let newNode = new Node(value);
        if(!this.first) {
            this.first = this.last = newNode;
        } else {
            let oldNode = this.first;
            this.first = newNode;
            this.first.next = oldNode;
        }
        return ++this.size
    }
    // pop() method removes a node at the top (first)
    pop() {
        if(!this.first) return null;
        let removedNode = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--
        return removedNode.value
    }
}

Pseudocode for push():

The function should accept a value
Create a new node with that value
If there are no nodes in the stack, set the first and last property to be the newly created node
If there is at least one node, create a variable that stores the current first property on the stack
Reset the first property to be the newly created node
Set the next property on the node to be the previously created variable
Increment the size of the stack by 1, and return it

Pseudocode for pop():

If there are no nodes in the stack, return null
Create a temporary variable to store the first property on the stack
If there is only 1 node, set the first and last property to be null
If there is more than one node, set the first property to be the next property on the current first
Decrement the size by 1
Return the value of the node removed

Queue

class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    // enqueue() method adds a new node at the end (last)
    enqueue(value) {
        let newNode = new Node(value);
        if(!this.first) {
            this.first = this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
    }
    // dequeue() method removes a node at the beginning (first)
    dequeue() {
        if(!this.first) return null;
        let removedNode = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--
        return removedNode.value;
    }
}

Pseudocode for enqueue():

This function accepts a value
Create a new node using the value passed to the function
If there are no nodes in the queue, set this node to be the first and last property of the queue
Otherwise, set the next property on the current last to be that node, and then set the last property of the queue to be that node

Pseudocode for dequeue():

If there is no first property, just return null
Store the first property in a variable
See if the first is the same as the last (check if there is only 1 node). If so, set the first and last to be null
If there is more than 1 node, set the first property to be the next property of first
Decrement the size by 1
Return the value of the node dequeued

A bit more hassle to implement than just using Array, but this will make the data structure more optimized. I definitely recommend you to go check out the Data Structure Series blog post I wrote on Linked List to learn about it if you need a refresher or have a problem comprehending the code above.

4. Big O

Space Complexity:
- O(n)
- Space complexity of this data structure is linear, as the size of the list increase, so does the space
Push/Pop and Enqueue/Dequeue:
- O(1) Time Complexity
- If we were to utilize Linked List over Array, both Push/Pop and Enqueue/Dequeue's time complexity can be optimized to O(1). Furthermore, Linked List is not the only optimized way to implement Stacks and Queues, for example, you can create those classes using an object as its storage. Here's video on this implementation if you are interested, but as you can see, there are many ways to create Stack/Queue.

5. Helpful Resources

Data Structure Cheat Sheet (Interview Cake)
Also, here's a really well-summarized cheat sheet/visualizations on data structures.

Data Structure Series: Linked List

Chuck Choi — Mon, 09 Aug 2021 16:15:48 +0000

Introduction

We use forks to eat pasta, spoons to eat soup, and chopsticks to eat dumplings. Each silverwares have its advantages/disadvantages, hence working better than the other for the food that it interacts well with. Just like that, different data structures are better suited and perform better than the others based on the situations/use cases. They each have their pros and cons. Understanding these pros and cons can help you be a better programmer, as it will allow you to choose an appropriate data structure(s) based on the circumstances/goals you have, and it helps to drastically improve the performance of the algorithm being applied. Feel free to leave a comment if you have any questions!

1. What is Linked List?
2. Implementation in JavaScript
3. Helper Methods
4. Big O
5. Helpful Resources

1. What is Linked List?

A Linked List is a collection of data in a sequence, with each of the data referencing its next node (or previous node if it is a Doubly Linked List) from its 'head' to the 'tail'.

A Linked List is a type of data that is represented in a sequential collection. Each piece of data in that collection is called the node, which references its adjacent node in the sequence. The first node of a linked list is called the 'head', and the last node is called the 'tail'. There are two types of linked lists: Singly Linked List and Doubly Linked List. As the names suggest, Singly Linked Lists’ nodes are linked in only single direction, so each nodes references its next node. On the other hand, Doubly Linked Lists’ nodes reference both its previous and the next node. In summary, a Linked List is a collection of data in a sequence, with each of the data referencing its next node (or previous node if it is a Doubly Linked List) from its 'head' to the 'tail'.

It sounds a bit similar to a built-in data structure Array, doesn't it? The difference is that Arrays store each data in a consecutive manner in the memory meaning that the elements are stored next to each other. And each elements is indexed based on the position, and each element is directly accessible using those indices. Meanwhile, Linked Lists store each data anywhere in the memory, but the nodes reference their next and previous node. So in order to access a specific node in a Linked List, you need to traverse the list sequentially from its head or tail to the other end until you get to the node you are looking for.

Because of these differences, there are things that linked lists can do better than arrays, and vice versa:

Arrays can search faster

As we discussed, Arrays support random access, so we can access any elements in the (n)th index very quickly while Linked Lists support sequential access, so we have to start from the head or tail to the (n)th node or value of the node we are looking for, thus taking longer time to search an element.
Linked Lists can insert/delete faster

In order to insert or delete an element in the beginning or middle of an Array, you have to shift all of the elements on the right since its consecutive index positions will change. So inserting and deleting an element in an array can be costly unless you are inserting or removing the last element of the array (since there's no elements after the last element). With Linked Lists, inserting/deleting the first and the last element takes constant time since we just have to update the head/tail. Inserting/deleting an element in the middle can take linear time as well though, since you'd have to find the position to insert/delete by traversing the list one element at a time. However, there's no need to update all the elements that come afterwards, you just have to rearrange its adjacent nodes.

2. Implementation in JavaScript

Singly Linked List

// each node references its NEXT node
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

let SLL = new SinglyLinkedList();
let firstNode = new Node(16)
let secondNode = new Node(2)
let thirdNode = new Node(46)

// set the first new node as the SLL's head
SLL.head = firstNode;
SLL.length++;

// second as its next
firstNode.next = secondNode;
SLL.length++;

// the third as the second's next 
// while also setting it as a tail since it's the last one.
secondNode.next = SLL.tail = thirdNode;
SLL.length++;

// This SLL will look something like this:
// (16) => (2) => (46)

Doubly Linked List

// each node references both its NEXT and PREVIOUS node
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

let DLL = new DoublyLinkedList();
let firstNode = new Node(361)
let secondnode = new Node(99)
let thirdNode = new Node(4)

// set the first new node as the DLL's head
DLL.head = firstNode;
DLL.length++;

// second as its next, and head as its prev
firstNode.next = secondNode;
secondNode.prev = firstNode;
DLL.length++;

// the third as the second's next 
// while also setting it as a tail since it's the last one.
secondNode.next = DLL.tail = thirdNode;
thirdNode.prev = secondNode;
DLL.length++;

// This SLL will look something like this:
// (361) <=> (99) <=> (4)

We will set up a Node class which accepts a value and set it to its value, with its next property (and prev if Doubly Linked List) initialized to null. Linked List class will be a sequential collection of these nodes, which will have its head and tail. We will want to keep track of the list's length, and increment/decrement it every time a new node is added or removed. Since Singly Linked Lists's nodes only reference the next node and Doubly Linked Lists' nodes reference both their next and previous nodes, Singly Linked Lists are simpler but less powerful than Doubly Linked Lists.

If you were to implement a helper method to pop the last element of the list, it's easier to do that with Doubly Linked Lists as you simply have to remove the tail of the list, and set the new tail to be the previous node of the tail being removed. On the other hand, we can access the tail of the list, but will have to traverse the entire list and remember the previous node until you hit the tail so you can remove the tail and set the remembered previous node to be the new tail.

The main drawback of using Doubly Linked List vs Singly Linked List is that Doubly Linked List takes up more space than the Singly Linked List since you have to set each nodes' next and previous node. But in return, it opens up more doors to make your data and its algorithms efficient. With that being said, here are couple helper methods to utilize Linked Lists better. However, we will only focus on Doubly Linked Lists for this blog post.

3. Helper Methods (Doubly Linked List only)

push()

// accepts a value as an argument
// appends a new node with the value passed at the end of the list
push(value) {
    let newNode = new Node(value);
    if(!this.head) {
        this.head = this.tail = newNode;
    } else {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
    this.length++;
    return this;
}

Pseudo code:

Create a new node with the value passed to the function
If the head property is null, set the head and tail to be the newly created node
If the head is not null, set the next property on the tail to be that node
Set the prev property on the newly created node to be the tail
Set the tail to be the newly created node
Increment the length
Return the Linked List

pop()

// removes the last node (tail) of the list
pop() {
    if(!this.head) return undefined;
    let removedNode = this.tail;
    if(this.length === 1) {
        this.head = this.tail = null;
    } else {
        this.tail = removedNode.prev;
        this.tail.next = null;
        removedNode.prev = null;
    }
    this.length--;
    return removedNode;
}

Pseudo code:

If there is no head, return undefined
Store the current tail in a variable to return later
If the length is 1, set the head or tail to be null
Update the tail to be the previous Node
Set the new tail's next to null
Decrement the length
Return the node removed

unshift()

// accepts a value as an argument
// prepends a new node with the value passed at the beginning of the list
unshift(value) {
    let newNode = new Node(value);
    if(this.length === 0) {
        this.head = newNode;
        this.tail = this.head;
    } else {
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
    }
    this.length++;
    return this;
}

Pseudo code:

Create a new node with the value passed to the function
If the length is 0, set the head and tail to be the new node
Otherwise
- Set the prev property on the head to be the new node
- Set the next property on the new node to be the head property
- Update the head to be the new node
Increment the length
Return the Linked List

shift()

// removes the first node (head) of the list
shift() {
    if(this.length === 0) return undefined;
    let oldHead = this.head;
    if(this.length === 1) {
        this.head = null;
        this.tail = null;
    } else {
        this.head = oldHead.next;
        this.head.prev = null;
        oldHead.next = null;
    }
    this.length--;
    return oldHead;
}

Pseudo code:

If length is 0, return undefined
Store the current head property in a variable
If the length is one, set the head and tail to be null
Update the head to be the next of the old head
Set the head's prev property to null
Set the old head's next to null
Decrement the length
Return old head

get()

// accepts an index as an argument
// returns the node at the index passed
get(idx) {
    if(idx < 0 || idx >= this.length) return null;
    let count, current;
    if(idx <= this.length/2 ) {
        count = 0;
        current = this.head;
        while (count !== idx) {
            current = current.next
            count++
        }
        return current;
    } else {
        count = this.length-1;
        count = this.tail;
        while (count !== idx) {
            current = current.prev
            count--
        }
        return current;
    }
}

Pseudo code:

If the index is less than 0 or greater or equal to the length, return null
If the index is less than or equal to half the length of the list
- Loop through the list starting from the head and loop towards the middle
- Return the node once it is found
If the index is greater than half the length of the list
- Loop through the list starting from the tail and loop towards the middle
- Return the node once it is found

set()

// accepts an index and value as arguments
// finds the node at the index, and updates the node's value to the value passed
// returns false if the node is not found, true if the value is updated
set(idx, value) {
    let foundNode = this.get(idx);
    if(!foundNode) return false;
    foundNode.value = value;
    return true;
}

Pseudo code:

Create a variable which is the result of the get method at the index passed to the function
If the get method does not return a valid node, return false
Set the value of the node found from get method to the value passed to the function
return true

4. Big O

Space Complexity:
- O(n)
- Space complexity of this data structure is linear, as the size of the list increase, so does the space
Push/Pop and Shift/Unshift:
- O(1) Time Complexity
- It will take constant time to add/remove the node at the head and tail of a Linked List, since we just have to add a new node to the either end, and update the newly added node as its head/tail, or its previous/next element as head or tail if the node is being removed.
Get/Set and Insert/Delete:
- O(n) Time Complexity
- In order for us to find an element in a Linked List, we will need to traverse the list to find the index or value of the index. Due to this nature of the Linked List, modifying the node in the middle of the list will take linear time (the time complexity changes based on the list size). Although Insert/Delete methods are not listed in the helper method above, you get the idea that we will have to traverse the list to find an index of the list to insert/delete the element.

5. Helpful Resources

Data Structure Cheat Sheet (Interview Cake)
Also, here's a really well-summarized cheat sheet/visualizations on data structures.

Let’s Talk About Cross-Origin Resource Sharing (CORS)

Chuck Choi — Sat, 22 May 2021 13:07:50 +0000

Access to fetch at ‘https://coolserver.com’ from origin ‘http://localhost:3000’ has been blocked by CORS policy: No ‘Access-Control-Allow-Origin’ header is present on the requested resource. If an opaque response serves your needs, set the request’s mode to ‘no-cors’ to fetch the resource with CORS disabled.

Every web developer may have come across this CORS policy violation (Cross-Origin Resource Sharing) error message at least once in their career. I faced this issue for the first time when I was developing a full stack application for a group project at a coding bootcamp. We were simply building a client application that was fetching data from the server we developed, and we panicked as this error popped up.

The error itself is actually pretty informative. It basically tells you that the client-side is not one of the "whitelisted" origins to access the data being fetched. In this blog post, lets learn the basics of Cross-Origin Resource Sharing, three scenarios and the common errors.

What is Cross-Origin Resource Sharing?

Let's first go over what CORS is and why it is important. CORS is an acronym for Cross-Origin Resource Sharing, which is a cyber security mechanism that allows/prevents one origin to access a resource from a different origin. This is something that the server has control over to restrict who has access to the resource, how they can access the data (which HTTP methods are allowed), if cookie information should be included or not, and etc.

Client-side applications are generally very vulnerable to cyber attacks from the malicious users. If you think about it, users can easily open the browser dev tool to check how the DOM is structured, which server it is communicating with, and where the resource is coming from without much restrictions. CORS is not the perfect security measure, but it provides minimum guarantee that the resource we fetch from the other origin is safe.

Same-Origin Policy vs Cross-Origin Resource Sharing

There are two policies that helps the browsers to protect the users from potential cyber attacks via dynamically loaded code. These are Same-Origin Policy (SOP) and Cross-Origin Resource Sharing. Generally, it is forbidden to read data from another origin. SOP allows browsers to only request resources from the same origin. You'd be violating SOP if you request a resource from a different origin. For example, requesting data from https://chuckchoi.me to https://dev.to would be violating SOP normally since these are not the same origin.

This would defeat the purpose and the power of the web if you are not able to fetch data from another origin. Thankfully, Cross-Origin Resource Sharing (CORS) allows exceptions to SOP and permits cross-origin requests to be made. There are three main requests used in cross-origin requests, and let's dive into the common errors you would see for each of them.

Before We Begin...

I built a simple client-side React app and an Express server to help us visualize what's going on. There's three different Cross-Origin requests you can test and see common errors you may face based on the server's setting. You can see each scenario's server and request structure, and click "Send Request" button to see what response you would get. You can also open your browser console to check the network tab to see the network behavior. Feel free to use the app on the side to supplement the understanding and check out the repository if you'd like!

CORS Tutorial App Link

Git Repository

Simple Request

There isn't an official terminology for the request we are about to discuss, but MDN's CORS documentation call it Simple Request. Simple Request is a cross origin request that is simply sent without any preflight request (which we will go over next) directly to the server. Server would respond back with a response that contains Access-Control-Allow-Origin in the header which then the browser checks CORS policy violations.

Simple Requests are only allowed if certain conditions are met which is not the case for most of the modern web development. Here are the list of conditions found in MDN:

One of the allowed methods:
- GET
- HEAD
- POST
Apart from the headers automatically set by the user agent (for example, Connection, User-Agent, or the other headers defined in the Fetch spec as a “forbidden header name”), the only headers which are allowed to be manually set are those which the Fetch spec defines as a “CORS-safelisted request-header”, which are:
- Accept
- Accept-Language
- Content-Language
- Content-Type (but note the additional requirements below)
The only allowed values for the Content-Type header are:
- application/x-www-form-urlencoded
- multipart/form-data
- text/plain
If the request is made using an XMLHttpRequest object, no event listeners are registered on the object returned by the XMLHttpRequest.upload property used in the request; that is, given an XMLHttpRequest instance xhr, no code has called xhr.upload.addEventListener() to add an event listener to monitor the upload.
No ReadableStream object is used in the request.

Wow, that was a pretty long list of requirements. As we discussed, it is pretty rare to meet all the requirements above in modern web development, so you may be dealing with preflight or credentialed request most of the time. But for Simple Request to work without violating CORS error, the response's header needs to have Access-Control-Allow-Origin with the request's origin listed or use an asterisk (* sign) as a wildcard to allow all origins.

Simple Request Exercise -- CORS Tutorial App

Error #1: No Access-Control-Allow-Origin Header

Let's go ahead and open up the CORS-Tutorial App. Under the Simple Request tab -> Error 1 tab, this is how the server is structured:

The fetch method we are invoking is fetch('https://cors-tutorial-server.herokuapp.com/api/simple/no-origin'). By default, fetch() would make a GET request to the URL passed as an argument if the method is not specified. And since the request is very basic, it is sending it as a simple request as it meets the simple request's requirements. Let's go ahead and click the button to see what would response we would get if we make a simple fetch request to that route:

Based on the error message above, the request we made from the app's origin https://chuckchoiboi.github.io/cors-tutorial/ has been blocked due to the violation of the CORS policy. It shows that "No 'Access-Control-Allow-Origin' header is present on the requested resource."

Solution 1: Wildcard Origin

One of the first steps to comply with the CORS policy is adding Access-Control-Allow-Origin to the response's header. You could either specify the origin, or use asterisk as a wildcard to allow all origins. From the server-side, you could add a wildcard origin like this:

Go ahead and try sending the request. You would see the server responding with a valid response like this:

Error #2 - Unmatching Origin

Allowing all origins is probably not the best practice and it would not be secure. It would be better if you "whitelist" the origins by specifying which ones you are expecting. Here's an example of a server with origin specified (Simple Request tab -> Error 2 tab):

The origin that this route is expecting is https://www.website.notcool though. Making a fetch request from https://chuckchoiboi.github.io/cors-tutorial/ show a bit different error message this time:

This time, the error shows that the origin the server is expecting for this route is https://www.website.notcool. Let's say we are making a request from www.website.notcool, but the protocol we are making the request from is http:// and not https://. This will throw the same error since origin consists of protocol and host both.

Solution #2: Matching Origin

With that being said, the server's response header would need to have the origin that matches the request's origin. A valid simple request can be sent to a server with the origin specified like this (Simple Request tab -> Valid Condition tab):

Preflight Request

You are going to come across preflight requests more than simple requests in modern web applications. For this scenario, the browser makes a preflight request to ask for permissions before the actual request is made. If the browser approves the response from the server through the preflight request, then the actual request is made. If the preflight request is not approved, then the actual request is not made.

During this preflight process, the preflight request uses OPTIONS method. The preflight response needs to allow the origin of the request in the header, and the actual request's method needs to be allowed as well. Once these conditions are satisfied, that's when the actual request is made.

Preflight Request Exercise -- CORS Tutorial App

Error #1: Preflight Response with Unmatching Origin

Take a look at this example. The request is trying to make a DELETE request to the server. Since the request is using DELETE method, it will make this request a preflight request, thus the browser will first send a preflight request using OPTIONS method to check its permission. However, since the origin of the request and the response's Access-Control-Allow-Origin value is not matching, this preflight request will fail and not even go to the actual request.

Error #2: Preflight Response with Method Unspecified

Let's try again. Let's try sending a DELETE request this time to a route with preflight response that contains header with the request's origin allowed like this:

Does it feel like we may be missing something? Here's a little spoiler. This one again will not even go to the actual request because the server's preflight response does not have DELETE method specified. Here's the error response you will get:

Error #3: Preflight Passes, Actual Request Fails

Now that the preflight response has matching origin allowed, and DELETE method allowed as well, this will send the actual DELETE request. Did you notice anything wrong from the response header though?

You got it right! As the error shows, the server is only allowing https://www.website.notcool origin. Even if the preflight passes, if the actual request fails, you will still be violating CORS policy.

Solution

In order to make a valid Preflight Request, the server needs to handle preflight request with valid origin, and valid method in the response header as we discussed. Once the preflight request passes, the actual request is sent. The actual request would need to have the request origin allowed to comply with the CORS policy.

Credentialed Request

Last but not least, there's a 3rd scenario to cross-origin request that strengthens the security. When sending XMLHttpRequest or fetch, you should not include the browser cookie or authentication-related headers without any options. Sending a request with credentials option would allow us to send sensitive information like cookies in cross-origin requests.

You can send a credentialed request by adding {"credentials": "include"} option to the request in JavaScript. This will add some strict rules to CORS policy conditions. When the browser is sending a credentialed request, the response's Access-Control-Allow-Origin should not be using the wildcard "*". It needs to specify the request's origin, and also the server needs to have additional header Access-Control-Allow-Credentials set to true to allow valid credentialed request to be made.

Credentialed Request Exercise -- CORS Tutorial App

Error 1: Wildcard Origin

This time, we are sending a GET request using fetch() method that includes {"credentials":"include"} as an option. The server's response header is using a wildcard for Access-Control-Allow-Origin. Let's go ahead and send the request by clicking the button in the app.

As you can see from the error message, credentialed request does not allow Access-Control-Allow-Origin to be the wildcard. In order for us to be able to make a credentialed request to the server, we will need the server's route to allow https://chuckchoiboi.github.io.

Error 2: Access-Control-Allow-Credentialed

Okay we have the request origin https://chuckchoiboi.github.io specified in the server this time. Without further ado, let's go ahead and click the "Send Request" button!

Trust me, this is the last error you are going to see today. As we discussed earlier, credentialed request adds more strict conditions to CORS policy rules. What the error message is suggesting is that the response header needs to include an additional header Access-Control-Allow-Credentials with its value being set to true.

Solution

To summarize, credentialed request can be made by adding {"credentials":"include"} in the request, response header specifying the request origin (wildcard not allowed), and Access-Control-Allow-Credentials is set to true in the response header as well. A successful credentialed request should look something like this:

Conclusion

When I think of Cross-Origin Resource Sharing, it reminds me of guest list/access to a gated community. I've been to couple of my friends' gated community houses, where the home owners have to give names to the security guard at the gate to let them know who is invited to enter the gate.

What's interesting about Cross-Origin Resource Sharing is that the front-end developers are the ones who actually have problems with CORS policy violations, while the backend developers have the control to resolve these issues in the response header. Resolving CORS errors is not too difficult to handle, you just need to communicate with the backend developer to make sure all the CORS policy conditions are met to fetch the resource.

Thank you so much for taking time to read this blog post! If you want to learn about the React app or the Express server I built, or give me feedback on the app/blog post feel free to message me on LinkedIn!

A Reflection of a Coding Bootcamp Grad

Chuck Choi — Mon, 17 May 2021 17:04:27 +0000

After 6 months of the coding bootcamp journey, a cohort of 18 brilliant programmers has graduated on May 15th, 2021, and we all got one step closer to our goals. It was definitely not an easy road especially with the COVID-19 Pandemic forcing us to be in a virtual setting, but we all powered through! I wanted to take a moment to give a shoutout to my fellow cohort members and share what it was like to be a part of it for those who are debating whether to commit to a coding bootcamp or not.

Personal Background

I came from a restaurant management background and switched to the tech industry in 2018. For the past 3 years, I've been working at a Boston-based tech company named HubSpot. The company has been very supportive of my interest in front-end development, so I had the pleasure to take various front-end courses and training under their financial support. I really enjoyed front-end development and wanted to become a software engineer eventually. Coming from a non-tech background, I wasn't sure where to start though.

I heard about General Assembly's Software Engineering Immersive course from a colleague but wasn't quite sure if I wanted to commit to such a course that is time-consuming and expensive yet. I broke down my income to see if I could cover the cost but I barely could. I knew my wallet would be very slim for a while, So I did research on Lambda School, Hack Reactor, Flatiron School, and a local university's Bootcamp program to make a careful decision. I checked out each of their cost/financial options they had, and how the class structure looked like. After going through months of emails, calls, and Google searches, I decided to go with General Assembly.

Course Breakdown

Institution
- General Assembly
Course Name
- Software Engineering Immersive
Dates
- November 17th, 2021 - May 15th, 2021 (6 months)
Setting
- Part-time, Virtual
Tuition
- $14,950 USD
Schedule

Tuesday	Wednesday	(Every other) Thursday	Saturday
5:30 PM - 9:45 PM	5:30 PM - 9:45 PM	5:30 PM - 7:30 PM	9:00 AM - 5:00 PM

General Assembly had a fairly positive reputation and was the best for me because I have taken a couple of courses at that institution, so I was already satisfied with them. Most importantly, they offered a part-time class that fit my schedule and an alumni discount...!

Financial Detail

Tuition was one of the most important factors for me when deciding whether to enroll in the program or not, and I bet it was for many of the Bootcamp grads/prospects. General Assembly's tuition was $14,950 which was kind of in the middle of the other bootcamp's price range. GA had a couple of financing options like loans and income share agreement to make it workout for the students. They offered a 15% alumni discount for me which brought down the cost by a significant amount (went from $14,950 to $12,707.50). And thankfully, my employer provided $5,000 of financial support to take this course, so I ultimately had to pay $7,707.50 out of my pocket.

Typical Day to Day

I took this course while working full-time 7:00 AM to 4:00 PM. On the days I had the class, I had to work out, cook, and eat from 4:00 PM - 5:30 PM, then I was off to class for about 4 hours. Thanks to the course being virtual and not in-person, it saved me tons of time. I initially thought about taking the in-person course at GA but COVID-19 forced everything to be virtual. I do not know how I would've done it if it was in-person, driving through the LA traffic every class.

I sacrificed my free time so I wouldn't lose much sleep. I missed out on Friendsgiving dinner this year which I was sad about. There were less golf time, video games, and Netflix. But it felt really good to be learning with organized time management and seeing my progress.

This is how my typical day-to-day looked like:

The Course Experience

First of all, my cohort was pretty awesome. There were total 18 students who came from various backgrounds like music, media, aerospace, technical support, customer success, consulting, construction, fresh out of high school and etc. Some of the students had no prior coding experience, and some students had prior knowledge/experience that supplemented the course material. But we all had moments we struggled and triumphed. But we all powered through, it was fascinating to see everyone's growth through the journey.

The course covered Front-End, Full-Stack, and client/server-side frameworks. The course was taught via Zoom and GitHub, so we got very familiar with GitHub thanks to that. The course was structured like this:

Lecture
In-class exercise
Lab work
Homework
Projects
Career support/consulting (Every other Thursday)

The course work covered enough for you to learn the basics of each topic, but you really needed to put time outside of the class to get the best out of the class. I spent a lot of time after class to review, write codes from scratch to practice what I learned, and some of us even had peer-review sessions to help each other learn. Although the class was virtual, we had a lot of chances to get close to each other. There were two solo projects and two group projects, and the group projects really gave us chance to see each others' work styles and get close.

Also, the instructors were the best part of the course! There were two instructors and an assistant instructor teaching the course, and all of them were very patient. If there were students who were behind, they took time to set up breakout rooms and office hours to make sure that no one was left behind. I really appreciated their dedication and effort.

There was room for growth for this program though. The course was led using the GitHub repository that I believe the General Assembly HQ put together to align it with the industry standards. There were many moments that some of us felt that the repository was pretty outdated with documentation on the tech stacks we were learning. That definitely caused so much confusion figuring it out and debugging the version issues. Although it is understandable that it can't be perfect due to the tech stacks changing so much during a short period of time, we thought it would help the students focus more on comprehending the fundamentals of the material. I have sent this feedback to GA team, so hopefully this will be reflected in the future by making sure that the instructions are up to date more frequently.

Personal Advice

I got lucky to get discounts and financial supports, but when I say this is a big financial and time commitment, I mean it. Some people would have to quit their job to be able to take this course and not having an income for 3 months/6 months would give you a lot of stress. So if you are considering enrolling in a coding bootcamp, really do some research on if you are able to financially support yourself, if you have time for it, and if this course would really be beneficial for you. There are many other ways to gain programming knowledge -- online classes and documentations to teach yourself how to code!

Coding bootcamp is not a golden ticket to a software engineering career. You really need to invest a lot of time and dedication to learn, never stop learning, work on projects, and prep for interviews/coding challenges to land a job. It all depends on the individual's dedication and capacity.

Conclusion

If you do not think you have what it takes to be a programmer, I want to tell you that many of us felt that way too. I had moments I doubted myself and wanted to cry. It was manageable but not easy working full-time and being enrolled in a coding bootcamp part-time for 6 months. I had many nights I was digging deeper into the course material, homework, projects, and extra stuff I was curious about which made me messed up my sleeping schedule pretty often. I actually lost a lot of hair, but no big deal -- I have Kirkland's Minoxidil by my side (hair growth treatment). My hair may or may not grow but one thing I was sure of: my technical knowledge will.

Thank you for taking time to read this article.
Connect with me on LinkedIn and let me know if you have any questions!

How Does The Web Work?

Chuck Choi — Mon, 26 Apr 2021 13:38:41 +0000

Car, television, stove, and refrigerator are the machines we use daily that are fairly simple to use. These are essential tools in our lives yet most of us do not fully comprehend how they work but still, it is not the end of the world. We don't have to understand their mechanisms to be able to use them. Computers and mobile devices are also other machines that most people know how to use, but they are pretty complicated machines that are capable of doing many things.

Using these devices, we connect to the World Wide Web (www) commonly known as the Web where we can access various resources such as documents, audios, pictures, and videos. The web became very simple to use despite its complexity over time, and even a 7-year-old Larry can open his mom's iPad to watch his favorite cartoon on YouTube.

Have you ever wondered what's happening behind the scenes for someone like young Larry to go on YouTube to play the video, or what the moving pieces are for you to get to a website? You came to the right place. Let us go over the key players of the web to do its work.

The history of the World Wide Web

The World Wide Web, also known as the web was invented by a British computer scientist named Sir Tim Berners-Lee back in 1989. His parents were computer scientists, but Tim was more interested in trains growing up. He got into electronics as he had to build electronic gadgets to control the trains. Eventually, he got more interested in electronics than trains which is how he started working on computers and software.

Tim became a software engineer at a physics laboratory in Switzerland named CERN after graduating from Oxford University. Back then, things were very manual and offline which you had to log on to different computers to get the information stored. Some computers used different programs, so you had two choices: learn a different program on each computer to access the information, or go have a coffee chat with your co-worker to ask how they work.

With millions of computers being connected together through the internet, Tim envisioned a technology to connect the world with information and proposed his idea to his supervisor at CERN. Although it was never an official project, his supervisor gave him time to work on the big task.

Tim has developed the three fundamental technologies by 1990 that are the foundation of the web today: HTML, URI, and HTTP. Over time, the web has grown and Tim realized that the web's true potential would only prevail if it was accessible by anyone, anywhere without any cost or permission. CERN agreed to make the web free forever and announced the decision in April 1993. The web has grown ever since with the number of websites totaling 1.8 Billion as of April 2021.

“Had the technology been proprietary, and in my total control, it would probably not have taken off. You can’t propose that something be a universal space and at the same time keep control of it.” - Sir Tim Berners-Lee

Modern Days of the Web

Enough of the history lessons on the web, it's time to talk about how the offspring of Tim's noble task look like today. To summarize the flow of the web, a browser sends an HTTP request to a server to access specific content, and the server returns an HTTP response of that requested data back to the browser. We will get into more detail but it looks something like this:

Let's go through each of the key players of the web.

Client, Server, and HTTP

I spend a lot of free time watching YouTube. It is probably the website I spent the most time in my life. In order for me to get to the website to watch a video, I go through these steps:

Open my computer
Open Google Chrome
In the browser, I type www.youtube.com
I get to the website
Watch a video

In this example, I am the client who requests access to a video that is in YouTube's database. YouTube is serving me by providing the web service to access the video, which makes YouTube the server.

A client is internet-connected computer hardware that uses client software like a web browser. Your computer and mobile device are clients that use browsers like Chrome, Firefox, or Safari. We often refer to the device, browser, and user using the device as clients. Clients can request access to the content that servers store.

On the other hand, a server is computer software and its hardware that serves clients by receiving their requests and returning responses accordingly. Servers can show web pages, send/receive emails, store files and share them, or identify and authorize user accounts.

I like to compare a client and a server relationship as a patron and a librarian at a public library. The patron can ask the librarian a book he is looking for, and the librarian will respond with the location of the book if they have a copy of it. Just like that, a client can send a request to a server to view a web document.

When humans speak to each other, we use a shared language and follow its grammar structure to deliver our messages across. Clients and servers do the same by using Hypertext Transfer Protocol (HTTP) which is a request-response protocol they expect from each other when exchanging data.

A client communicates with a server by sending an HTTP request containing information on what the client is looking for, and the server responds to the client by returning an HTTP response as a result of the request. HTTP requests and responses both have HTTP Header, which allows clients and servers to understand each other better. HTTP Headers contain information like the client's setup (browser, operating system), browser cookie, and domain name the client wants to reach.

HTTP response often contains the resource data that was requested, and the status of the requested action to indicate if it was successful or not. As the name "Hypertext" suggests, HTTP requests and responses transfer content that is beyond just text. The content could be code files like HTML, CSS, JavaScript, or assets like images, audio, video, documents, and etc.

It is possible for hackers to intercept the data in the middle and see the data being exchanged though. This could result in horrible outcomes logging into a bank account, email, or health insurance. That is why Hypertext Transfer Protocol Secure (HTTPS) was introduced to encrypt the data. With HTTPS, hackers will see encrypted meaningless characters even if they were to intercept the data. The data can be decrypted by using the shared secret key between the client and the server.

Internet, TCP/IP, and DNS

For clients and servers to be able to communicate, they connect to the global system of computer networks called the Internet. We pay a monthly fee to the internet service providers (ISP) to be able to connect to the network. The internet uses the internet protocol suite (TCP/IP) to exchange data packets between computers.

These packets are fragments of data that allow data to be transferred reliably and efficiently. Transferring a large file instead of packets would be inefficient as the speed of the data transfer varies based on how you are sending them (optical cable, copper wire, or satellite). It can result in an unexpected loss of data or a change in the order of the packets. this is where the internet protocol suite comes into play.

The internet protocol suite is a communication protocol that ensures the successful exchange of data to an intended destination. It consists of two protocols: TCP and IP.

TCP stands for Transmission Control Protocol which defines the model of the data and assigns numbers to each data packet being transferred. With the numbers assigned to each packet, it can detect loss of data during the transfer to fix them and reassemble them in the right order as one file again. Due to its complexity, it makes TCP very reliable.

In order for data to get to the right place between computers, it requires the addresses of each computer. IP stands for Internet Protocol which routes data to the right location. IPs are numbers of unique computer addresses with a mix of digits and periods like 192.158. 1.38 (IPv4). With the web growing its size every day, a new version of IP, IPv6 was deployed to fulfill the need for more internet addresses. Compared to its previous version with a 32-bit binary IP address, IPv6 uses a 128-bit binary IP address which allows 340 undecillion unique address space! Here's an example of an IPv6 address: 2001:0db8:85a3:0000:0000:8a2e:0370:7334.

These IP addresses are not that human-readable though, and we'd need address books to keep all the websites' IP addresses. And it'd be very inconvenient if we had to look up Google's IP address and type http://142.250.188.238/ in the browser to get there every time. To solve this problem, the Domain Name System (DNS) was introduced. The DNS is like the address book of the internet. We purchase domains from DNS providers, website addresses that are more human-readable like google.com, youtube.com, or facebook.com. With the domains purchased for the websites, the DNS provider is responsible for exchanging domain URLs to IP addresses to the clients.

Typical Flow of the Web

With that being said, let's take a look at an example of a user accessing YouTube's home page and break down what's happening behind the scenes:

User opens his laptop (client) that is connected to the internet and opens Google Chrome (browser)
User types in the web address www.youtube.com to the browser address bar
The browser goes to the DNS server and exchange the web address into an IP address
The browser uses the IP address to make an HTTP request to YouTube's server to access the website page
YouTube server looks at the HTTP request, prepares the data into packets and TCP numbers each packet (many companies have their data stored in services like Oracle Cloud or AWS)
YouTube server responds with an HTTP response with a "200 OK" status code (means the request was processed successfully) to the user's browser
TCP assembles the packets back to the data as a whole, and the web page is displayed by parsing HTML, CSS, JavaScript and its assets like images and videos

Conclusion

Imagine the world without the web. Imagine doing your school projects without any access to Google, just like back a couple of decades ago when things were simple without any power of the internet. You would have to access offline documents like books, newspapers, or magazines. Researchers had to fly across the country to interview the right personnel to collect data.

The web has made many things possible by connecting humanity all over the world to exchange information. You can now watch Netflix anywhere with the internet instead of going to a Blockbuster store to rent a DVD, have video chats with friends and family across the globe, or simply Google any information you are looking for. Especially the COVID-19 pandemic really showed the power of the web by connecting the world regardless of the location. It minimized the damage to our society by allowing remote work, food delivery service, and quick/easy access to COVID-19 guidelines for anyone.

Although you do not have to fully understand how the web works to be able to use them, I hoped to provide a little bit of history and knowledge on how the web operates. Feel free to comment below with additional information! Thank you so much for taking time to read this blog post.

Follow my blog account or let's connect on LinkedIn to keep up with more tech content!

Is "this" really that complicated in JavaScript?

Chuck Choi — Mon, 19 Apr 2021 15:03:31 +0000

this keyword can be one of the most confusing monsters in JavaScript. Especially those who didn't learn JavaScript as their first programming language find it pretty confusing as it behaves differently in JS compared to the other languages. And many programmers rely on libraries like jQuery, so they learn how to use it but don't get to fully comprehend its fundamentals. Well, let me show you how this isn't as confusing as you think.

What is "this" in JavaScript?

MDN Web Doc explains that this is:

A property of an execution context (global, function or eval) that, in non–strict mode, is always a reference to an object and in strict mode can be any value. In most cases, the value of this is determined by how a function is called (runtime binding). It can't be set by assignment during execution, and it may be different each time the function is called.

To put it simply, this is a keyword used to reference the execution context. We could think of it as "whoever it is that calls the function." So this typically refers to the object that is invoking its method. In JavaScript, any value can be determined when it is defined or when the function is called. The latter is the case for this keyword usually in the case of Implicit binding.

With Implicit binding, the value of this is determined based on the execution context. But this behaves differently if the function being invoked as an arrow function or if you are using strict mode introduced in ES5. And there's Explicit binding which you can explicitly bind this keyword to an object you pass as an argument for call(), bind(), and apply() methods. Let's dive in deeper to each of them.

1. Object Method

Take a look at the following code:

  var hi = {
    myName: 'Slim Shady',
    myNameIs: function() {
      console.log(this.myName);
    }
  }

  hi.myNameIs();  // prints 'Slim Shady'

The above code's hi object has a method myNameIs which logs myName of this in the console. When hi object invokes its method like the following hi.myNameIs(), the object who called the function is hi which makes this to be implicitly bound to hi object. Hence, the console will log myName of the object 'Slim Shady'. A simple way to look at it is that whatever is on the left side of a dot notation of a method being invoked is the object that this will be referring to.

How about this example though:

  function whatIsThis() {
    console.log(this);
  }

  whatIsThis(); // prints Window {...}

Hmm... we just discussed that an easy way to understand this keyword in object method invocation is paying attention to the left side of dot notation. But this time, whatIsThis is a function defined using function declaration, and we can execute it without an object which logs this as the window object.

Sounds pretty confusing right? Well, when we declare a function, we are making it a global function available to the global object, so the function's containing scope is the global object Window. Another way to execute whatIsThis is: window.whatIsThis(). Look at that, window is on the left side of whatIsThis()! This brings me to the next point -- this in global context.

2. Global Context

As we discussed, when a method inside an object is executed by the object, this refers to the object. But what happens if I try to simply log this into console? Give it a try in your browser.

  console.log(this); // prints Window {...}

Looks like this refers to window object. By default, this refers to the global object (Window in browser environment). If we want to understand why it is, ask yourself (or Google) what the window object is. If we take a look at MDN Web Docs again, it explains:

The window object is the Global Object in the Browser. Any Global Variables or Functions can be accessed as properties of the window object.

When we add this to your browser console, your global environment Window is executing the expression this, so the window object is being referred to in this global context.

Back to the Slim Shady example, here's a function created using the myNameIs method in hi object earlier:

  var hi = {
    myName: 'Slim Shady',
    myNameIs: function() {
      console.log(this.myName);
    }
  }

  var hisNameIs = hi.myNameIs;

  hisNameIs(); // prints undefined

Interesting. hisNameIs function logged undefined in the console. Let's try to understand what happened at the line var hisNameIs = hi.myNameIs.

First, hi.myNameIs is a method -- a property containing a function definition. We simply declared a global function named hisNameIs by using var and initialized it with the function definition from hi object passed.

Second, global functions are stored as properties in the window object. When we invoke the global function hisNameIs(), it is the same as window.hisNameIs(). The window is the object that is executing its method hisNameIs, so this is now referring to the window object. window object does not have a property named myName, so it will return undefined.

In conclusion, this will refer to the global object in global context.

3. Strict Mode

JavaScript was first introduced in 1995 as Mocha which took 10 days to develop by a Netscape programmer named Brandon Eich. It would be surprising if the language came out to be perfect in 10 days of development right? The language has evolved to today's version 6 (ES6), with the language designers' attempt to correct the flaws in the past versions. Its legacy features were not possible to be removed in order to maintain the backward compatibility, which is why strict mode was introduced in ES5 to opt in to correct the early language flaws.

this keyword is one of them. It behaves differently when you opt into strict mode:

  function whatIsThis() {
    "use strict";
    console.log(this);
  }

  whatIsThis(); // prints undefined

In strict mode, this keyword will default to undefined in function invocation. It is likely that this keyword was not meant to point to the window object, as you can simply use window keyword to do so.

In ES5, bind() method was introduced to explicitly set the function's this regardless of how it is called. You can pass an object as an argument when using bind() method, and the function's this keyword will refer to the object no matter how the function is invoked. Bringing back the code from earlier using bind() method this time, we can now create a new function with object passed explicitly like this:

  var hi = {
    myName: 'Slim Shady',
    myNameIs: function() {
      "use strict"
      console.log(this.myName);
    }
  }

  var hisNameIs = hi.myNameIs.bind(hi)

  hisNameIs(); // prints Slim Shady

Boom! Even with the strict mode, hisNameIs function's this will refer to the hi object passed no matter what. call() and apply() are basically the same which you can pass additional arguments to the function. The three methods are slightly different which you can read more about in this blog post.

4. Arrow function

this inside an arrow function behaves a bit differently compared to the one inside a function declaration or a function expression. Arrow function was introduced in ES6 as an alternative to a traditional way of defining function. Let's compare these two objects using the different versions of function:

// using regular function as callback inside forEach()
var oldPhone = {
    owner: 'Chuck',
    apps: ['Facebook', 'YouTube', 'Uber'],
    useApps: function () {
        this.apps.forEach(function(app) {
            console.log(this.owner + ' is using ' + app)
                        // this refers to the window object
        })
    }
}

oldPhone.useApps()
// prints undefined is using Facebook
// prints undefined is using YouTube
// prints undefined is using Uber

oldphone.useApps function iterates each of the apps using forEach with a regular function passed as a callback function. However, the callback function inside forEach method does not bind to the original object. Instead, it will bind to the global window object thus this.owner returns undefined.

This could be very inconvenient if we were doing something similar as a class. There are two ways to fix it though, forEach() method takes an optional argument thisArg in addition to the callback function like this: arr.forEach(callback[, thisArg]).

Or we can use an arrow function as a callback to utilize its lexical scoping:

// using arrow function as callback inside forEach()
var newPhone = {
    owner: 'Chuck',
    apps: ['Facebook', 'YouTube', 'Uber'],
    useApps: function () {
        this.apps.forEach((app) => {
            console.log(this.owner + ' is using ' + app)
        })
    }
}

newPhone.useApps()
// prints Chuck is using Facebook
// prints Chuck is using YouTube
// prints Chuck is using Uber

Voila! This time the callback function's this referred to newPhone, and logged this.owner as 'Chuck'. Arrow function allows you to write functions in a cleaner way, and they have lexical scope I mentioned earlier which means that they will inherit the scope from its parent.

The callback function nested inside the forEach method above inherited the scope from its parent useApps which is newPhone object. Because of this nature, The value of this inside an arrow function is determined when that arrow function is defined unlike the typical situations from earlier. I personally think that this inside an arrow function is the most confusing part of this keyword, but it simply inherits the scope from its parent.

NOTE
bind(), call(), and apply() are not compatible with arrow functions. Arrow functions will inherit the scope from its parent regardless.

Conclusion

To conclude, let's summarize how this works in JavaScript:

this is a keyword used to reference the execution context
In method invocation, the object that is invoking the method would be the execution context this will refer to
In global context like regular function invocation, this will default to the global object
In strict mode, this keyword will default to undefined in regular function invocation.
You can use bind(), call(), or apply() to explicitly bind an object to a function
An arrow function will inherit the scope from its parent, so this inside an arrow function will follow its parent's this
bind(), call(), and apply() do not work for arrow functions

Hope this was a helpful resource for you to understand how this works in JavaScript. Feel free to comment below if you have any questions or notice any inaccurate information and I will respond as soon as possible :)

Follow me on Clubhouse @chuckchoiboi

Forem: Chuck Choi

Data Structure Series: Hash Table

Introduction

Table of Contents

1. What is Hash Table?

2. Hash Function

3. Implementation in JavaScript

4. Helper Functions

5. Handling Collisions

6. Big O

7. Helpful Resources

Data Structure Series: Stack & Queue

Introduction

Table of Contents

1. What are Stacks and Queues?

Stack

Queue

2. Implementation Using Array

Stack

Queue

3. Implementation Using Linked List

4. Big O

5. Helpful Resources

Data Structure Series: Linked List

Introduction

Table of Contents

1. What is Linked List?

Arrays can search faster

Linked Lists can insert/delete faster

2. Implementation in JavaScript

3. Helper Methods (Doubly Linked List only)

4. Big O

5. Helpful Resources

Let’s Talk About Cross-Origin Resource Sharing (CORS)

What is Cross-Origin Resource Sharing?

Same-Origin Policy vs Cross-Origin Resource Sharing

Before We Begin...

Simple Request

Simple Request Exercise -- CORS Tutorial App

Preflight Request

Preflight Request Exercise -- CORS Tutorial App

Credentialed Request

Credentialed Request Exercise -- CORS Tutorial App

Conclusion

A Reflection of a Coding Bootcamp Grad

Personal Background

Course Breakdown

Financial Detail

Typical Day to Day

The Course Experience

Personal Advice

Conclusion

How Does The Web Work?

The history of the World Wide Web

Modern Days of the Web

Client, Server, and HTTP

Internet, TCP/IP, and DNS

Typical Flow of the Web

Conclusion

Is "this" really that complicated in JavaScript?

What is "this" in JavaScript?

1. Object Method

2. Global Context

3. Strict Mode

4. Arrow function

Conclusion