JS-Set

Photo by Oskars Sylwan on Unsplash

Javascript objects are great! But a little primitive.

The javascript object is a force to be reckoned with. It's very versatile, and is a great place to store simple key value pairs.
Got some characters to keep track of? Use an object. Have some numbers to keep track of? Use an object. Have some nodes to keep track of? Well...

Javascript Set

Again an {} is great for simple key value pairs. The keys are always going to be real simple. String's or if they are a number, they will be converted into a string. This is normally fine, and the values you store can still be complex, like a function or another object.

It's only an issue if you want your key to be more complex.

I was solving a little coding algorithm where I was looking to see if two linked lists had a shared intersection in common.

/*
  Intersecting
  2 - 3 - 7 \ 
            4 - 5 - 3
    9 - 10 /

  Not intersecting
  2 - 3 - 7

  9 - 3
*/

One thing I thought, is I could just iterate through one, and store all the references to them, since I've used this pattern in many problems involving strings, or numbers, as keys.

The issue is that a linkedList is made up of nodes, so it's a complex value. If I was just comparing the data property it would be fine, but I wanted to know if it was the exact same node not just one with the same data value.

// Ex Node:
node = {
  data:4,
  next: nextNode
}

Set

A quick heads up. This is not the most efficient way to solve this problem. Lookup in a set can be O(n), but it will allow us to store the complex data structure. Overall the solution I'm talking about was O(n^2) time complexity because you store one list, then loop through the other and do lookups in the set. I actually did a better solution at the time, but I wanted to actually implement it with a set because it may be useful down the road.

function inefficientIntersectingLists(ll1, ll2) {
  let firstNode = ll1
  let secondNode = ll2
  const setOfNodes = new Set()

  // insert into our set
  while (firstNode !== null) {
    setOfNodes.add(firstNode)
    firstNode = firstNode.next
  }
  // loop through second linkedList check for overlap
  while (secondNode !== null) {
    if (setOfNodes.has(secondNode)) {
      return secondNode
    }
    secondNode = secondNode.next
  }
  return 'No overlap'
}

Implementation

Easy to set it up. 😁.

  const setOfNodes = new Set()

You can add this to your repertoire

  setOfNodes.add(firstNode)

If your keys need to be complex the Set has what you need

  setOfNodes.has(secondNode)

Takeaways

Use a set when you have some complex values you want to store as keys. If you are just dealing with primitive values such as strings and numbers use an object since that has constant lookup time O(1). Here's some more information on set methods over at MDN.

If you don't care about sets at all, but now want to see the more optimal solution to the linked list overlap problem, check it out here.

Thanks for reading, maybe you will find a use case for this somewhere soon.

Happy Coding,

James