Image for post
Image for post
Photo by Nick Karvounis on Unsplash

#15 Data Structures with JS examples: Sets

{ rxluz }
{ rxluz }
May 27, 2020 · 11 min read

This article belongs to the JS Data Structures series, which contains these articles:

  • Arrays
  • Stacks
  • Queues
  • Linked List
  • Sets
  • Dictionaries/maps (soon)
  • Hashes tables (soon)
  • Trees: Binary Search Tree (BST) (soon)
  • Trees: AVL Tree (soon)
  • Trees: Red-black Tree (soon)
  • Trees: Binary Heap / Heapsort
  • Graphs (soon)

Set are a collection of sequential and unique elements, this structure doesn’t allow adding duplicate values, we have several examples of sets:

  1. The natural numbers {0, 1, 2, 3, 4, 5, 6, 7, 8 …}
  2. The followers/following list in any social network
  3. Some list with tags in blogs
  4. A shopping list
  5. A to-do list with unique items
Image for post
Image for post
A list with unique lists is a set!

This article will cover the following content:

  • Basic structure
  • Sets methods
  • Operations with sets
  • Using the ES6 Set
  • Instantiating our Set
  • Time and space complexity

Basic structure

Let’s create a function that will allow us to output only the public Sets methods. working like a closure, avoiding changes in internal attributes, the skeleton will be:

function Set() {
let items = {}
let size = 0
class PublicSet {
...the set methods will be here
}
return new PublicSet()
};

With this approach, the only public methods will be the methods included in PublicSet class, if you want to know more about closures this article is really useful:

Set methods

After we created the basic structure we are ready to implement the required set methods:

  • has: Returns if a set contains an item or not
  • add: Allows add a new item inside a set
  • delete: Remove a specific item from a set
  • clear: Remove all items from a set
  • size: Returns the set number of items
  • values: Returns how many items there are inside a set

Note: In order to create a set you need to create the method has before the other methods, once this will be used by the other methods.

has(item)
To check if the required item is inside our set, and we have some different ways to do that:

has(item) {
return items.hasOwnProperty(item)
}

Or:

has(item) {
return item in items
}

Or:

has(item) {
return typeof items[item] !== 'undefined'
}

I prefer the second approach because the syntax is nicer and cleaner than others.

add(item)
The process to add a new item is simple, first, we check if this item was not added before, if don’t we add this list to our set items.

In the end, we need increment our size variable.

add(item){
if(this.has(item)){
return false
}
items[item] = item
size++
return true
}

delete(item)
In order to remove some item, first, we need to check if the item was added before, so if we found the item we remove it.

Also, we need decrement the size variable.

delete(item){
if(!this.has(item)){
return false
}
delete items[item]
size--
return true
}

clear()
To clear all items from a set we need to restore the items and size variables to its original state.

clear(){
items = {}
size = 0
}

size()
In our approach, we are using the size variable to control the Set size, this helps to get the total without the need to traverse all items in our Set.

size(){
return size
}

Without this approach, we’ll need to use items.keys().length, the problem is when we use this we are using a slower operation to do that, in the time and complexity session this is better explained.

values()
To get all Set values we use the for..in loop:

values(){
let valuesList = []
for(let value in items){
valuesList.push(value)
}
return valuesList
}

Putting all together

If you want to check out other Javascript Data Structures examples take a look in this GitHub repository:

Operations with sets

Once sets are composed of unique elements we could compare one set with other and create different operations like union, intersection, difference and subset.

This operation allows joining two different sets to create a new one, example:

Set A = A,B,C,D

Set B = B,C,D,E

Union A with B = A, B, C, D, E

This concept could be visually represented by this picture:

Image for post
Image for post
Source: https://upload.wikimedia.org/wikipedia/commons/0/06/Set_union.png

To find the union set we need:

  1. Create the Sets.
  2. Call the union method that accepts as a parameter the second set.
  3. Get the values from both sets.
  4. Create a new union empty set where we will store the values.
  5. Traverse all elements from the first set and add all them in the union set.
  6. Traverse all elements from the second set and add all them in the union set.

As a result of these steps we have this code:

union(secondSet) {
const unionSet = new Set()
const firstSetValues = this.values()
const secondSetValues = secondSet.values()
firstSetValues.forEach(value => {
unionSet.add(value)
})
secondSetValues.forEach(value => {
unionSet.add(value)
})
return unionSet
}

We could reduce this code using the spread operator and removing the curly braces from the foreach loop:

union(secondSet) {
const unionSet = new Set()
const firstSetValues = this.values()
const secondSetValues = secondSet.values()
const allSetValues = [...firstSetValues, ...secondSetValues]
allSetValues.forEach(value => unionSet.add(value)) return unionSet
}

This operation allows creating a new set with the commons items in both sets, example:

Set A = a,b,c,d

Set B = b,c, d,e

Intersection A and B = b,c,d

This concept could be visually represented by this picture:

Image for post
Image for post
Source: https://upload.wikimedia.org/wikipedia/commons/c/cb/SetIntersection.svg

To find the intersection set we need:

  1. Create the Sets.
  2. Call the intersection method that accepts as a parameter the second set.
  3. Get the values from both Sets.
  4. Create a new Set where we will store the values.
  5. Traverse all elements from the first set checking if the value is also present in the second set, when is present in both we add this value in intersection set.
  6. Do the same with the second set

As a result of these steps we have this code:

intersection(secondSet) {
const intersectionSet = new Set()
const firstSetValues = this.values()
const secondSetValues = secondSet.values()
firstSetValues.forEach(value => {
if (secondSet.has(value)) {
intersectionSet.add(value)
}
})
secondSetValues.forEach(value => {
if (this.has(value)) {
intersectionSet.add(value)
}
})
return intersectionSet
}

We could reduce this code using the spread operator and removing the curly braces from the foreach loop:

intersection(secondSet) {
const intersectionSet = new Set()
const firstSetValues = this.values()
const secondSetValues = secondSet.values()
const allValues = [...firstSetValues, ...secondSetValues]
allValues.forEach(
value =>
secondSet.has(value) &&
this.has(value) &&
intersectionSet.add(value),
)
return intersectionSet
}

What we did inside our loop is an uncommon but efficient way to call a function only if some condition matches:

allValues.forEach(
value =>
secondSet.has(value) &&
this.has(value) &&
intersectionSet.add(value),

)

What’s happening here is, only if the first two conditions are true the function will be called, you could try it in your browser inspector to understand better how it works:

// this never displays 'hello world':
true && false && console.log('hello world')
// this will display 'hello world':
true && true && console.log('hello world')

This operation allows creating a new set with the elements in the first set that is not present in the second set, example:

Set A = a,b,c,d

Set B = b,c, d,e

Difference A and B =a

This concept could be visually represented by this picture:

Image for post
Image for post
Source: https://commons.wikimedia.org/wiki/File:SetDifferenceA.svg

To find the difference set we need:

  1. Create the Sets.
  2. Call the difference method that accepts as a parameter the second set.
  3. Traverse all elements from the first set checking if the value is also present in the second set, when is not present in the second we add this value in difference set.

As a result of these steps we have this code:

difference(secondSet) {
const differenceSet = new Set()
const firstSetValues = this.values()
firstSetValues.forEach(value => {
if (!secondSet.has(value)) {
differenceSet.add(value)
}
})
return differenceSet
}

This operation allows checking if the second sets is a subset of the first set, which means that all elements in a second set also is inside the first set, example:

Set A = a,b,c,d

Set B = b,c

Set c = b,c, d, e

B is subset of A=true

C is subset of A = false

This concept could be visually represented by this picture:

Image for post
Image for post
Source: https://commons.wikimedia.org/wiki/File:Set_subsetBofA.svg

To check if a second set is a subset of the first set we need:

  1. Create the Sets.
  2. Call the subset method that accepts as a parameter the second set.
  3. Traverse all elements from the second set checking if the value is also present in the first set and return true if all values match this condition or false if don’t.

As a result of these steps we have this code:

subset(secondSet) {
if (secondSet.size() < this.size()) {
return false
}
const firstSetValues = this.values() for (let value of firstSetValues) {
if (!secondSet.has(value)) {
return false
}
}
return true
}

We also could do the same using every js native method:

subset(secondSet) {
if (secondSet.size() < this.size()) {
return false
}

return this.values().every(value => secondSet.has(value))
}

Using the ES6 Set

We could use the native JS method Set to do what we did with our code, let’s try an example from MDN Sets documentation:

var mySet = new Set();

mySet.add(1); // Set [ 1 ]
mySet.add(5); // Set [ 1, 5 ]
mySet.add(5); // Set [ 1, 5 ]
mySet.add('some text'); // Set [ 1, 5, 'some text' ]
var o = {a: 1, b: 2};
mySet.add(o);

mySet.add({a: 1, b: 2}); // o is referencing a different object so this is okay

mySet.has(1); // true
mySet.has(3); // false, 3 has not been added to the set
mySet.has(5); // true
mySet.has(Math.sqrt(25)); // true
mySet.has('Some Text'.toLowerCase()); // true
mySet.has(o); // true

mySet.size; // 5

mySet.delete(5); // removes 5 from the set
mySet.has(5); // false, 5 has been removed

mySet.size; // 4, we just removed one value
console.log(mySet);// Set [ 1, "some text", Object {a: 1, b: 2}, Object {a: 1, b: 2} ]

Also, we could simulate our operations using ES6 Sets:

// from https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Setfunction isSuperset(set, subset) {
for (var elem of subset) {
if (!set.has(elem)) {
return false;
}
}
return true;
}
function union(setA, setB) {
var _union = new Set(setA);
for (var elem of setB) {
_union.add(elem);
}
return _union;
}

function intersection(setA, setB) {
var _intersection = new Set();
for (var elem of setB) {
if (setA.has(elem)) {
_intersection.add(elem);
}
}
return _intersection;
}


function difference(setA, setB) {
var _difference = new Set(setA);
for (var elem of setB) {
_difference.delete(elem);
}
return _difference;
}

//Examples
var setA = new Set([1, 2, 3, 4]),
setB = new Set([2, 3]),
setC = new Set([3, 4, 5, 6]);

isSuperset(setA, setB); // => true
union(setA, setC); // => Set [1, 2, 3, 4, 5, 6]
intersection(setA, setC); // => Set [3, 4]
difference(setA, setC); // => Set [1, 2]

Instantiating our Set

After declaring your Set, you could call it in this way:

const mySet = new Set();// adding items
mySet.add("a new item");
// searching for a item
mySet.has("a new item");
// getting the set size
mySet.size()
// getting all items inside a set
mySet.values()
// removing item
mySet.delete("a new item");
// removing all items inside a set
mySet.clear()

Time and space complexity

Time complexity defines how faster is your algorithm, and space complexity defines how much memory your algorithm needs to run, this is also called Big-O notation.

Image for post
Image for post
From http://bigocheatsheet.com/

Let’s analyse the methods inside our set to find out this:

  • add: We have O(1) to time and O(1) to space, once the time and memory that we need to run this operation remains the same regardless of the number of items inside our Set.
  • delete: Same thing here, O(1) to time and O(1) to space.
  • has: Differently from arrays we don’t need to traverse the items inside a set to check if an item exists or not, also we don’t need store any additional information in memory to run this operation, thus this is O(1) to time and O(1) to space.
  • clear: When we clear our set we simply redefine the items object to an empty one, this operation is O(1) to time and to space because will take the same time and memory regardless of the set size.
  • size: We are using the variable size to control the set length, with this approach this operation takes the same time and space even with millions of items, thus O(1) to time and space.
  • values: To get all items and output them in array format we need to transverse all items inside our set, push each one to a temporary array and output them, it means that bigger set will take more time and space to run this same operation, so O(n) to time and space.

Also, let’s check the time and space complexity of the Sets Operations:

  • union: To understand better let’s divide this algorithm into steps, and check the complexity of each one:
union(secondSet) {
const unionSet = new Set() // O(1) time and O(1) space
const firstSetValues = this.values() // O(n) time and O(n) space
const secondSetValues = secondSet.values() // O(n) time and O(n) space
firstSetValues.forEach(value => { // O(n) time and O(1) space
unionSet.add(value) // O(1) time and O(n) space
})
secondSetValues.forEach(value => { // O(n) time and O(1) space
unionSet.add(value) // O(1) time and O(n) space
})
return unionSet
}

When we put all together we have:

Time: O(1), O(N), O(N), O(N), O(1), O(N), O(1) = O(N)
Space: O(1), O(N), O(N), O(1), O(N), O(1), O(N) = O(N)

Thus O(n) both to space and time.

  • intersection: Same thing here O(n) to space and time.
  • difference: We need more time as we have more items, and more memory to store the result, so we have O(n) to space and time.
  • subset: This operation will take more time when you have more items, but will use the same memory regardless of the number of items, therefore is O(n) to time and O(1) to space.

If you want to know more about Big O Notation and how to calculate this I wrote this article that will help you:

If you to want to know more about Javascript and Data Structures I recommend these books:

  • You Don’t Know JS Serie by Kyle Simpson (My favourite)
  • Eloquent JS by Marijn Haverbeke
  • Head First Javascript by Michael Morrison
  • Secrets of the JavaScript Ninja by Bear Bibeault and John Resig
  • Learning JavaScript Data Structures and Algorithms by Loiane Groner

Thanks for reading! Feel free to hit the recommend button below if you found this article helpful, also, please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

If this post was helpful, please click the clap 👏 button below to show your support! ⬇⬇

Frontend Weekly

It's really hard to keep up with all the front-end…

{ rxluz }

Written by

{ rxluz }

Senior Software engineer @udemy. Writer, ECMAScript addict, React, NodeJS, coffee enthusiast.

Frontend Weekly

It's really hard to keep up with all the front-end development news out there. Let us help you. We hand-pick interesting articles related to front-end development. You can also subscribe to our weekly newsletter at http://frontendweekly.co

{ rxluz }

Written by

{ rxluz }

Senior Software engineer @udemy. Writer, ECMAScript addict, React, NodeJS, coffee enthusiast.

Frontend Weekly

It's really hard to keep up with all the front-end development news out there. Let us help you. We hand-pick interesting articles related to front-end development. You can also subscribe to our weekly newsletter at http://frontendweekly.co

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store