Introduction
Understanding algorithms and data structures are crucial to enhancing your performance 10x more than your peers who don't. This is because you analyze problems critically and devise the best means to solve them. It could mean speeding up server request times or finding the best way to store large data sets with minimal disk space.
This article aims to help you understand the basic concepts of algorithms and data structures and how to implement them using JavaScript.
What is an algorithm? An algorithm is a step-by-step set of instructions for accomplishing a task. Suppose you have a problem waking up early and you keep missing deadlines. How do you solve this? Aha! Set alarms. That is what an algorithm looks like.
Data structures, on the other hand, are ways of storing data efficiently.
Data structures and algorithms (DSA) are so vital that they are critical to the overall performance of a computer. The algorithm you choose will determine its running time(Big O Notation) or its efficiency. Some popular DSAs are binary search, recursion, sorting, arrays, linked lists, and hash tables.
What Is Binary Search?
Suppose you are searching for a name in a country's directory; it starts with a J. You could start at the beginning (from "A" countries) and keep flipping the pages till you get to the "J" list of countries(these countries are sorted alphabetically). If the country starts with a "Z", then you keep flipping to the end of the directory. This is known as a simple search algorithm. But imagine if this was a phone book directory with over 100,000 phone numbers, this is unimaginably hard. How do you optimize this? Binary search to the rescue.
The binary search algorithm takes a sorted list of elements as input, and if the element you are looking for is in the list, the binary search returns the position where it's located, else it returns null. Instead of going step by step to get to Japan, binary search divides this array into multiple parts and searches each of them accordingly.
This way, the search is fast.
Arrays
They are a collection of elements indexed by a key. Array elements are stored sequentially, with the key serving as an identifier in the collection. Its indexes start with 0.
They are super useful because retrieving or sorting any element takes constant time O(1). it can also be used to implement many other data structures that place additional restrictions on how the data is manipulated. A string, for example, may be implemented as an array of characters.
Here is an implementation of arrays and binary search in JavaScript.
function binary_search(list, item) {
let guess = list.find(element => element == item);
if (guess) {
return guess + "\ncountry index no: " + list.findIndex(country => country === guess);
}
return null + ": element is not in the array"
}
console.log(binary_search(country_list, 'Japan')); // Japan | country index no: 109
console.log(binary_search(country_list, 'Cookie')); // null: element is not in the array
Sorting Algorithm
Sorting is seldom used by programmers. It's mostly handled already by the language or libraries they code in. The JavaScript language, for example, sorts arrays using insertion sort, heap sort, or quick sort.
Heapsort is similar to the Javascript array-filter method. It divides the input into a sorted region and an unsorted region and iteratively moves elements to the sorted region. Here’s an example;
Linked List
A linked list is a data structure where every element contains both data and a pointer to the next element in the list. A distinguishing feature of a linked list is that its items can be scattered anywhere in memory. This is not true for arrays. See some examples below;
What are Hash Tables?
Hash tables are lists of arbitrary elements in an array. The element to be stored or its key is used as an index in the array. Here is an example:
The hash function converts the key of the elements to be placed into a hash, then maps the hashed elements to a specified spot in the table. Each of these elements can also be a sub-array of arbitrary elements in the table.
Recursion
Recursion is a coding technique used in many other algorithms. It is a shortcut to lengthy code and may not offer any performance gain except for the programmer.
Suppose you found a treasure suitcase. To unlock this case, you need to grab a key from a box with other smaller boxes, that may still have other boxes in them.
One approach is to make a pile list of boxes to search through, then look through each of these boxes. If you find a key, great! If not, add the new empty box to the pile list to search through later.
Recursion removes the step where you add the new empty box found to a search list. It calls the search method immediately on the new empty found box. Here is an example in Javascript;
const suitCase = new Map();
suitCase.set('box-0', '')
.set('box-1', '')
.set('box-2', '')
.set('box-3', '')
.set('box-4', 'key')
.set('box-5', '')
.set('box-6', '');
function search (suit) {
for (let [key, value] of suit) {
if (value === 'key') {
console.log(`Found ${value} at ${key}!`);
}
}
}
search(suitCase); // prints Found key at box-4!
You found the key, Tada!
In summary, DSA is a great way to think effectively as a programmer. It gives you tools for solving hard problems. Click on the GitHub repository link to download all the code snippets used in this article. Happy Hacking!
Image Copyright by: Manning Publications, drawn by adit.io