# #15 Data Structures with JS examples: Sets

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

• Arrays
• Stacks
• Queues
• 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

• 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
• 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.

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:

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:

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:

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:

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 okaymySet.has(1); // truemySet.has(3); // false, 3 has not been added to the setmySet.has(5);              // truemySet.has(Math.sqrt(25));  // truemySet.has('Some Text'.toLowerCase()); // truemySet.has(o); // truemySet.size; // 5mySet.delete(5); // removes 5 from the setmySet.has(5);    // false, 5 has been removedmySet.size; // 4, we just removed one valueconsole.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;}//Examplesvar setA = new Set([1, 2, 3, 4]),    setB = new Set([2, 3]),    setC = new Set([3, 4, 5, 6]);isSuperset(setA, setB); // => trueunion(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 itemsmySet.add("a new item");// searching for a itemmySet.has("a new item");// getting the set  sizemySet.size()// getting all items inside a setmySet.values()// removing itemmySet.delete("a new item");// removing all items inside a setmySet.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.

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 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

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

Written by

Written by

## { rxluz }

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