In the last few weeks, I've been reading A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow. This book is great if you already have some experience programming and you want to level up your knowledge of these topics. So far, the algorithms parts have been great, but if you ask me, the most insightful and revealing part for me has been the data's structure.
If you're coming from a CS degree or similar background, these topics could be a piece of cake and surely you'll be familiar with it. But for those that come from a very different background and made a bootcamp or are self-taught, these topics sometimes are ignored. Because when we start, we're taught that our code initially should work. And it's ok if we are starting, but later when we begin to gain more experience, besides finding a code that works, we should find efficient and readable code.
And that's where data structures come. Yes, they give us structure and order. But the most important thing it's they help us with the effiency, because each structure performs differently in each context and operations.
Data Structure Operations
To understand the performance of any data structure we'll usually refer to four basic operations: reading, searching, inserting and deleting.
Arrays
The array is the most basic data structure in computer science. In essence, an array it's a chunk of memory where you can store a simple list of data elements. The arrays have a very useful property that it's their length. This property returns us the number of elements within the array. Also, each element in an array has an index: a number that identifies where a piece of data it's stored inside the array. In terms of efficiency, reading an element inside an array is very efficient and it'll cost us one step. For searching, it'll depend on the search algorithm we use, but if for example, we use a linear search, for an array of N elements, it could cost us a maximum of N steps. Insertion could take us a maximum of N + 1 step (this is the case if we want to insert an element in the first index of the array). On the other hand, deletion could take us a maximum of N steps. As we could see, inserting and deleting elements at the end of the array it's very efficient, but if we want to make this at the beggining of the array, it won't have the same effiency.
let animals = ['dog', 'cat', 'lion', 'bird'];
// Length property
console.log(animals.length); // 4
// Reading. Want to know the value stored in certain index
console.log(animals[2]); // 'lion'
// Searching.
// Want to know if a string of value 'bird',
// and if it exist, we want to know the index
const valueToFind = 'bird';
const indexOfValue = animals.findIndex((animal, index) => {
console.log(`${index + 1} step`);
return animal === valueToFind;
});
console.log(indexOfValue);
// Counting steps
// '1 steps'
// '2 steps'
// '3 steps'
// '4 steps'
// Index of the searched value
// '3'
// Inserting
// First, in the end of the array
animals.push('wolf');
console.log(animals); // ['dog', 'cat', 'lion', 'bird', 'wolf']
// Now in the middle
animals.splice(1, 0, 'tiger');
console.log(animals); // ['dog', 'tiger, 'cat', 'lion', 'bird', 'wolf']
// Deleting
//First, in the end of the array
animals.pop();
console.log(animals); // ['dog', 'tiger, 'cat', 'lion', 'bird']
// Now in the middle
animals.splice(2, 1);
console.log(animals); // ['dog', 'tiger, 'lion', 'bird']
Hash Tables (Objects)
A hash table is a list of paired values. The first item in the pair is called key, and the second item is called the value. The biggest perk in this structure is that reading and inserting are incredibly fast. Also, if we have data that it's related in pairs, hash tables are a natural data structure for organizing this data. For example, if you have a list of items with their prices:
{'Blue jean': 105, 'Yellow shirt': 45, 'Green Jacket': 78}
The magic of the hash table resides in the pairing of the key-value. Because of that, the cost of reading and insertion is O(1) (one step). If we don't know the keys, we cannot take advantage of these benefits.
In JavaScript, the most common implementation of hash table is the Object. In the Objects, we can pair the keys with values or functions. The values are called properties and the functions are called methods. For accessing or reading the values of the keys, we can use either the dot notation (object.key) or the bracket notation (object['key']) notations.
const myHashTable = {
prop1: 'I am the value of this property or key.',
method1: function () {
console.log('I am logging inside a method');
},
};
console.log(myHashTable.prop1); // 'I'm the value of this property or key'
// Calling the method with bracket ([]) notation
myHashTable['method1'](); // 'I am logging inside a method'
For insertion and delete we could see the next example:
const myObject = {
prop1: 'Hello',
};
myObject.insertedProp = 'I am inserted';
delete myObject.prop1;
console.log(myObject); // { insertedProp: "I am inserted" }
Also, another implementation of hash tables in JavaScript are Maps. They are similar to Objects but with important differences. For example, the keys in the Maps could be any value (functions, objects, or any primitive). In Objects, the keys must be either a String or a Symbol. Also, the Map is an iterable, the object doesn't implement naturally the iteration protocols. If you are interested in viewing all the differences you can check in the MDN documentation.
Sets
Set is a data structure that doesn't allow duplicate values to be contained within it. It's a simple list of values but with the constraint of only allowing unique values. JavaScript uses hash tables for implementing Sets.
// Create Set
const mySet = new Set();
// Insetions
// For insertion we use the method .add()
mySet.add(1); // Set(1) { 1 }
mySet.add(5); // Set(2) { 1, 5 }
// Doesn't allow inserting a repeted value
mySet.add(5); // Set(2) { 1, 5 }
// Searching
// For searching and checking if a value exist,
// we use the method .has()
mySet.has(1); // true
mySet.has('dog'); // false
// Delete
mySet.delete(5); // Removes 5 from set
mySet.has(5); // false
One of the most useful uses that we can give to sets is to eliminate repeated data within an array:
// Use to remove duplicate elements from an array
const numbers = [2, 3, 2, 4, 4, 5, 21];
// Here we make a Set starting from an array
// The conversion eliminate duplicate data
// Later we transform the Set to an array using the spread operator (...)
console.log([...new Set(numbers)]);
// [2, 3, 4, 5, 21]
In the next post we'll continue reviewing other data structures, like Stacks, Queue and other ones.
Thank you for reading. See you in the next post.
Top comments (0)