By Paul Ryan
Translation: Crazy geek
Original text: blog.logrocket.com/know-your-j…
Reproduced without permission
What are we talking about?
In JavaScript, data structures are often ignored or not touched much. However, for many large companies, it is generally required that you have a deep understanding of how to manage data. Mastering data structures can also help you solve problems.
In this article, the data structures we will discuss and implement are:
- The stack
- The queue
- The list
- Hash table
- The tree
The stack
The first data structure is the stack. It’s very similar to queues, and you’ve probably heard of call stacks before, which are JavaScript methods for handling events.
The stack looks like this:
The last item on the stack will be the first item to be removed. This is called LIFO (last in first Out). The back button in a Web browser is a good example: add each page you view to the stack, and when you click “Back,” the current page (the last page added) pops up from the stack.
Enough theory. Let’s look at some code:
class Stack {
constructor() {
// Create a stack structure, which is an empty object
this.stack = {}
}
// push a value to the top of the stack
push(value) {
}
// Pops the value at the top of the stack and returns
pop() {
}
// Reads the last value in the stack, but does not delete it
peek() {
}
}
Copy the codeI have commented the above code, now let’s implement it. The first method is push.
Think about what needs to be done with this method:
- We need to accept a value
- The value is then added to the top of the stack
- You should also track the stack length to know the index of the stack
If you can try it yourself first, that’s great. The full push method is implemented as follows:
class Stack {
constructor() {
this._storage = {};
this._length = 0; // This is the stack size
}
push(value) {
// Add values to the top of the stack
this._storage[this._length] = value;
// Since we have increased the length by one, we should also increase the length by one
this._length++;
}
/ / /...
}
Copy the codeI bet it’s easier than you think. There are many structures like this that sound more complicated than they are.
Now the POP method. The goal of the POP method is to remove the last value added to the stack and then return it. If possible, please try to implement it yourself:
class Stack {
constructor() {
this._storage = {};
this._length = 0;
}
pop() {
// we first get the last val so we have it to return
const lastVal = this._storage[--this._length]
// now remove the item which is the length - 1
delete this._storage[--this._length]
// decrement the length
this._length--;
// now return the last value
return lastVal
}
}
Copy the codeCool! It’s almost done. The last is the peek function, which looks at the last item on the stack. This is the simplest function: you only need to return the last value. Implementation is:
class Stack {
constructor() {
this._storage = {};
this._length = 0;
}
/* * Adds a new value at the end of the stack * @param {*} value the value to push */
peek() {
const lastVal = this._storage[--this._length]
return lastVal
}
}
Copy the codeSo it is very similar to the POP method, but does not remove the last item.
Yes! The first data structure has been implemented. Then there are queues, which are very similar to stacks.
The queue
Let’s talk about queues — hopefully stacks are still fresh in your mind, because they’re very similar to queues. The main difference between stacks and queues is that queues are first-in, first-out (FIFO).
It can be graphically represented like this:
So the two main methods are enqueue and dequeue. Data is added to the tail of the queue and removed from the head. To better understand it, let’s start implementing queues.
The core code structure is as follows:
class Queue {
constructor() {
// As before, we provide an object for the data structure
// There is also a variable to hold the length
this.queue = {}
this.length = 0
// This is a new variable that tracks the header
this.head = 0
}
enqueue(value) {
}
dequeue() {
}
peek() {
}
}
Copy the codeFirst implement the enqueue method. The purpose is to add an item to the end of the queue.
enqueue(value) {
// Add the length + head key to the object with the value argument
this.queue[this.length + this.head] = value;
this.length++
}
Copy the codeThis is a very simple way to add a value to the end of the queue, but you might call this.queue[this.length + this.head] = value; Confused.
Suppose the queue looks like {14: ‘randomVal’}. When we add this, we want the next value to be 15, so it should be Length (1) + head(14), which is 15.
The next implementation is dequeue:
dequeue() {
// Get a reference to the first value so it can be returned
const firstVal = this.queue[this.head]
// Now remove it from the queue
delete this.queue[this.head]
this.length--;
// Finally add our head to become the next node
this.head++;
}
Copy the codeThe last thing to implement is the peek method, which is very simple:
peek() {
// Just return the value
return this.queue[this.head];
}
Copy the codeThe queue is complete.
The list
Let’s talk about powerful linked lists first. This is much more complex than the above structure.
Maybe your first question is why do you use linked lists? Linked lists are primarily used in languages that do not have dynamically resizing arrays. Linked lists organize items in order, with one item pointing to the next.
Each node in the linked list has a data value and a next value. In the figure below, 5 is the data value and the next value points to the next node, which is 10.
Visually, it looks like this:
In an object, the LinkedList above looks like the one below
You’ll see that the last value of next, 1, is null because this is the end of the LinkedList.
So how do you do that?
Let’s create a LinkedList with values 1, 2, and 37.
const myLinkedList = {
head: {
value: 1
next: {
value: 2
next: {
value: 37
next: null}}}};Copy the codeNow we know how to create a LinkedList manually, but we need to code the method that implements the LinkedList.
The first thing to notice is that the LinkedList is just a bunch of nested objects!
When constructing a LinkedList, we need a head and a tail that both point initially to the head (because head is first and last).
class LinkedList {
constructor(value) {
this.head = {value, next: null}
this.tail = this.head
}
}
Copy the codeThe first method to implement is insert, which is used to insert a value at the end of the list.
// Insert will be added to the end of the list of links
insert(value) {
/* Create a node */
const node = {value, next: null}
/* Set tail's next property as a reference to the new node */
this.tail.next = node;
/* The new node is now the tail node */
this.tail = node;
}
Copy the codePerhaps the most confusing line above is this.tail.next = node. We do this because when we add a new node, we also want the current tail to point to the new node, which will become the new tail. When node is first inserted, the next pointer to the head points to the new node, just as in the constructor, where this.tail = this.head is set.
You can also go to the site for a graphical demonstration that will help you understand the insertion process (press Esc to get rid of the annoying pop-up window).
The next method is to delete the node. We first have to decide whether the argument is a value or a reference to a node (in an interview, it’s a good idea to ask the interviewer first). We pass a “value” in our code. Removing nodes from the list by value is a slow process because you have to traverse the entire list to find the value.
Here’s how I do it:
removeNode(val) {
/* Start with head */
let currentNode = this.head
/* We need to keep the reference to the previous node */
let previousNode
/* When a node exists, it means that the tail */ has not been reached
while(currentNode) {
/* If you find the value you want, exit the loop */
if(currentNode.value === val) {
break;
}
/* Set currentNode to previousNode */ if no value is found
previousNode = currentNode
/* Get the next node and assign it to currentNode */
currentNode = currentNode.next
}
/* Returns undefined because no node with the value */ was found
if (currentNode=== null) {
return false;
}
// If the node is head, set head to the next valueHead of the nodeif (currentNode === this.head) {
this.head = this.head.next;
return;
}
/* Remove a node by setting it to the previous node */
previousNode.next = currentNode.next
}
Copy the codeThe removeNode method gives us a good idea of how LinkedList works.
So again, first set the variable currentNode to the head of the LinkedList, since this is the first node. Then create a placeholder variable named previousNode that will be used in the while loop. The while loop starts with the condition currentNode and continues as long as currentNode exists.
The first step in the while loop is to check if there is a value. If not, set previousNode to currentNode and currentNode to the next node in the list. Continue this process until I find the value I need to find or I have traversed the node.
After the while loop, if there is no currentNode, false is returned, meaning that no node was found. If a currentNode does exist, check if the currentNode is head. If so, set the head of the LinkedList to the second node, which will become head.
Finally, if currentNode is not the head, set previousNode to point to the node before currentNode, which will remove currentNode from the object.
Another common method, which interviewers may also ask you about, is removeTail. This method does what it says, but removes the last node of the LinkedList. This is much easier than the above method, but it works similarly.
I suggest you try it out for yourself, and then look at the following code (we don’t use tail in the constructor to make it a bit more complicated) :
removeTail() {
let currentNode = this.head;
let previousNode;
while (currentNode) {
/* tail is the only node that does not have a next value, so if there is no next value, then the node is tail */
if(! currentNode.next) {break;
}
// Get a reference to the previous node
previousNode = currentNode;
// Move to the next node
currentNode = currentNode.next;
}
// To remove the tail, set previousNode.next to null
previousNode.next = null;
}
Copy the codeThese are some of the main methods of LinkedList. There are other ways to do linked lists, but with what you’ve learned above, you should be able to implement them yourself.
Hash table
Next up is the powerful hash table.
A hash table is a data structure that implements an associative array, which means it maps keys to values. A JavaScript object is a “hash table” because it stores key-value pairs.
Visually, it can be expressed like this:
Before we discuss how to implement hash tables, we need to discuss the importance of * hash functions. * The core concept of a hash function is that it takes input of any size and returns a fixed-length hash value.
hashThis('i want to hash this') = >7
Copy the codeHash functions can be very complex or straightforward. Every file on GitHub is hashed, which makes finding each file very fast. The core idea behind a hash function is that given the same input the same output will be returned.
After introducing the hash function, it’s time to discuss how to implement hash tables.
The three operations to be discussed are insert, get and finally remove.
The core code for implementing hash tables is as follows:
class HashTable {
constructor(size) {
// Define the size of the hash table that will be used in the hash function
this.size = size;
this.storage = [];
}
insert(key, value) { }
get() {}
remove() {}
// This is how the hash key is calculated
myHashingFunction(str, n) {
let sum = 0;
for (let i = 0; i < str.length; i++) {
sum += str.charCodeAt(i) * 3;
}
returnsum % n; }}Copy the codeNow tackle the first method, insert. Insert into the hash table looks like this (for simplicity, this method will simply handle collisions) :
insert(key, value) {
// Get the index in the array
const index = this.myHashingFunction(key, this.size);
// Handle collisions - if the hash function returns the same index for different keys,
// In complex hash functions, collisions are likely
if (!this.storage[index]) {
this.storage[index] = [];
}
// push a new key-value pair
this.storage[index].push([key, value]);
}
Copy the codeCall the insert method like this:
const myHT = new HashTable(5);
myHT.insert("a".1);
myHT.insert("b".2);
Copy the codeWhat do you think our hash table will look like?
You can see that the key-value pairs have been inserted into the table at indexes 1 and 4.
Now implement deleting from the hash table
remove(key) {
// Get the index of key first, remember,
// The hash function always returns the same index for the same key
const index = this.myHashingFunction(key, this.size);
// Remember that we can have multiple arrays at one index (unlikely)
let arrayAtIndex = this.storage[index];
if (arrayAtIndex) {
// Iterate over all arrays at the index
for (let i = 0; i < arrayAtIndex.length; i++) {
// get the pair (a, 1)
let pair = arrayAtIndex[i];
// Check whether the key matches the parameter key
if (pair[0] === key) {
delete arrayAtIndex[i];
// The work is done, so exit the loop
break; }}}}Copy the codeFinally, the get method. This is the same as the remove method, but this time, instead of deleting it, we return the pair.
get(key) {
const index = this.myHashingFunction(key, this.size);
let arrayAtIndex = this.storage[index];
if (arrayAtIndex) {
for (let i = 0; i < arrayAtIndex.length; i++) {
const pair = arrayAtIndex[i];
if (pair[0] === key) {
return pair[1]; }}}}Copy the codeI don’t think you need to do this because it does the same thing as the remove method.
You can argue that it is not as complicated as it first appears. This is a data structure that is used everywhere, and one that is well understood!
Binary search tree
The last data structure is the infamous binary search tree.
In a binary search tree, each node has zero, one, or two child nodes. The one on the left is called the left child and the one on the right is called the right child. In a binary search tree, the left subterm must be smaller than the right subterm.
You can represent a binary search tree like this:
The core classes of the tree are as follows:
class Tree {
constructor(value) {
this.root = null
}
add(value) {
// We will implement it below}}Copy the codeWe will also create a Node class to represent each Node.
class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right; }}Copy the codeLet’s implement the Add method. I’ve commented out the code, but if you find it confusing, remember that all we need to do is start at the root and check left and right for each node.
add(value) {
// If there is no root, create one
if (this.root === null) {
this.root = new Node(value);
return;
}
let current = this.root;
// keep looping
while (true) {
// If the current value is greater than the value passed in, go left
if (current.value > value) {
// If there are left child nodes, the loop is repeated
if (current.left) {
current = current.left;
} else {
current.left = new Node(value);
return; }}// The value is small, so we are on the right track
else {
/ / to the right
// If there are left child nodes, run the loop again
if (current.right) {
current = current.right;
} else {
current.right = new Node(value);
return; }}}}Copy the codeTest the new add method:
const t = new Tree();
t.add(2);
t.add(5);
t.add(3);
Copy the codeNow the tree looks like this:
To better understand this, let’s implement a method that checks if the tree contains a value.
contains(value) {
// Get the root node
let current = this.root;
// When a node exists
while (current) {
// Check whether the current node has this value
if (value === current.value) {
return true; // Exit the function
}
// Determine the next current node by comparing our value to current-. value
// If small, go left, otherwise go right
current = value < current.value ? current.left : current.right;
}
return false;
}
Copy the codeAdd and Contains are the two core methods of binary search trees. An understanding of these two methods can make you better able to solve problems in your daily work.
conclusion
I’ve covered a lot of ground in this article, and having this knowledge will put you in a good position for an interview. Hopefully you’ll learn something and be able to breeze through technical interviews (especially those pesky whiteboard interviews).