Photo by Alina Grubnyak on Unsplash
Data structures are the foundation of computer science and programming. We use data structures for retrieving, organizing, processing, and storing data. By learning the different data structures, you can become a better developer, comparing algorithms, choosing wisely libraries to use in each scenario, and implementing outstanding and cost-effective solutions.
A deep understanding of data structures is also an excellent skill for technical interviews in big companies.
In this article, I will explain the principal data structures and demonstrate how to implement them with JavaScript, but you can apply its concepts in any programming language.
Understanding Sets
A set is a collection of unique elements of any type. It can contain strings, numbers, objects, and even other sets. The concept of sets comes from set theory , and we can easily implement the operations for manipulating them with JavaScript.
To create sets in JavaScript, we can use the Set() class:
const set = new Set();
set.add({ value: 3, weight: 2 });
set.add("string");
set.add(true);
console.log(set);
// Output: Set(3) { { value: 3, weight: 2 }, 'string', true }
To implement set operations, we can use the Set() class methods as follows:
// Union
const union = (firstSet, secondSet) => {
const setUnion = new Set(firstSet);
for (const element of secondSet) {
setUnion.add(element);
}
return setUnion;
};
// Intersection
const intersection = (firstSet, secondSet) => {
const setIntersection = new Set();
for (const element of secondSet) {
if (firstSet.has(element)) setIntersection.add(element);
}
return setIntersection;
};
// Difference
const difference = (firstSet, secondSet) => {
const setDifference = new Set(firstSet);
for (const element of secondSet) {
setDifference.delete(element);
}
return setDifference;
};
You can use sets to implement various algorithms and even other data structures. Different from arrays, sets are flexible data structures you can use to store any kind of data.
Understanding Stacks
A stack is a collection of elements where the insertion and removal follows a specific order ( last-in, first-Out ). The concept of stacks comes from queuing theory. Like a stack of plates, where you can’t remove the plate at the bottom, in a stack, you can only add or remove an item at the top of the stack.
We can implement stacks with a dynamic structure, which doesn’t have a fixed size and can grow dynamically, or with a static structure, which has a fixed size and can’t store more items them a defined limit.
To implement stacks with static structure in JavaScript, we can create a new class as follows:
export class Stack {
constructor(maxLength) {
this.items = new Array();
this.maxLength = maxLength;
}
push(item) {
if (this.isFull()) return "Overflow";
else return this.items.push(item);
}
pop() {
if (this.isEmpty()) return "Underflow";
else return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
isFull() {
return this.items.length === this.maxLength;
}
}
const stack = new Stack(3);
stack.push(100);
stack.push(101);
stack.push(102);
stack.pop();
console.log(stack.peek());
// Output: 101
Use case
Now, let’s see a simple example of how to use a stack. Imagine you are developing a text editor and it needs to track the last file changes, so users can undo or redo the changes. You can use a stack to track file changes as follows:
import { Stack } from "./stack.js";
export class Editor {
constructor() {
this.lastChanges = new Stack(50);
}
async write(writable, input) {
await writable.write(input);
return this.lastChanges.push(input);
}
async undo(writable) {
const lastChange = lastChanges.peek();
await writable.remove(lastChange);
return this.lastChanges.pop();
}
async redo(writable, input) {
return await this.write(writable, input);
}
}
In the example above, whenever we write an input to the file, the method also adds the change to the lastChanges stack invoking the method push().
Whenever we undo a file change, the method gets the last change by invoking the method peek(), next remove it from the file, and remove it from the lastChanges stack by invoking the method pop().
Understanding Queues
A queue is a collection of elements where the insertion and removal follows a specific order. Stacks and queues are similar, but different from stacks, queues are first-in, first-out structures, which means the first element to be added will be the first element to be removed.
Depending on the requirements, we can implement a circular queue , which is a queue that reuses empty slots. Circular queues need to manage the free space in an array by pointing to the front and back indexes after enqueueing or dequeuing an element.
We can also implement a priority queue, where some items have priority over others. In that case, we must enqueue an item with high priority in front of items with low priority.
To implement linear queues with static structure in JavaScript, we can create a new class as follows:
export class Queue {
constructor(maxLength) {
this.items = new Array();
this.maxLength = maxLength;
}
enqueue(item) {
if (this.isFull()) return "Full";
else return this.items.push(item);
}
dequeue() {
if (this.isEmpty()) return "Empty";
else return this.items.shift();
}
front() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
isFull() {
return this.items.length === this.maxLength;
}
}
Use case
Now, let’s see an example using a queue. Imagine you are developing a feed with an infinite scroll for a social media app. As the user scrolls down the feed, you need to simultaneously load new posts and unload posts already seen, for performance reasons. You can use a queue to load and unload the posts as follows:
import { Queue } from "./linearQueue.js";
export class Feed extends Queue {
constructor(height) {
super(height);
}
get() {
if (this.isEmpty()) return "The feed is empty";
else return this.items;
}
async load() {
const post = await fetch("https://api.co/userfeed/post/");
return this.enqueue(post);
}
unload() {
return this.dequeue();
}
}
In the example above, we can invoke the load() and unload() methods to display the posts correctly as the user scrolls down the feed, loading new posts and removing those already seen.
Understanding Hash Tables
A hash table is a structure that stores data in key-value pairs, hashing the key and storing it as an index. The algorithm applied to convert the key in a hash value is called hash function. Hash tables are especially useful when you need fast searching.
A common problem with hash tables is collisions, which occur when the hash function produces the same hash for different keys.
We can handle collisions with two different methods: linear probing and chaining. I won’t explain these methods in this article, but I recommend you to go deeper into this topic as probably you will have to deal with collisions.
We can easily implement a hash table in JavaScript by creating a class as follows:
export class HashTable {
constructor() {
this.size = 0;
this.table = new Array(255);
}
#hash(key) {
let hash = 0;
for (let index = 0; index < key.length; index++)
hash += key.charCodeAt(index);
return hash % this.table.length;
}
set(key, value) {
const index = this.#hash(key);
this.table[index] = { key, value };
this.size++;
}
get(key) {
const index = this.#hash(key);
return this.table[index];
}
remove(key) {
const index = this.#hash(key);
if (this.table[index]) this.table[index] = undefined;
this.size--;
}
}
In the implementation above, the hash function is a private method that gets the ASCII code of every character of the key and applies the remainder operator to ensure that the hash key is in the valid range of table indexes (as the table is an array with limited size), producing a numeric index for every key-value pair stored.
Use cases
A classic use case of hash tables is database indexing. Hash tables can be used in database engines to create indexes of specified columns in database tables so that it doesn’t need to scan entire tables when querying.
Hash tables can also be used to create in-memory caching systems, where the data needs to be stored and retrieved really fast.
Next steps
There are other important data structures in addition to those explained. In the next post, I will explain graphs and trees with examples and use cases using JavaScript, so if you are interested subscribe so you don’t miss the article.
To help deepen your knowledge of the data structures explained, I recommend these free resources:
- Sets operations : https://isaaccomputerscience.org/concepts/data_numsys_set_operations
- Stacks : https://isaaccomputerscience.org/concepts/dsa_datastruct_stack
- Queues : https://isaaccomputerscience.org/concepts/dsa_datastruct_queue
- Hash tables : https://isaaccomputerscience.org/concepts/dsa_datastruct_hash_table
Conclusion
Thanks for reading! Keep studying the different data structures and don’t miss my next article where I will explain trees and graphs with JavaScript. Let me know your thoughts in the comments section, and consider following me for more articles like this.
Top comments (0)