Sets: How a Single Rule Can Affect Efficiency

Let’s explore this other data structure: the set. A set is a data structure that does not allow duplicate values to be contained within it.

Sets are of different types, but for this discussion, I’ll talk about an array-based set. This set is just like an array—it’s a simple list of values. The only difference between this set and a classic array is that the set never allows duplicate values to be inserted into it.

For example, if you had the set ["a", "b", "c"] and tried to add another "b", the computer just wouldn’t allow it, since a "b" already exists within the set.

Sets are useful when you need to ensure that you don’t have duplicate data.

For instance, if you’re creating an online phone book, you don’t want the same phone number appearing twice. In fact, I’m currently suffering from this with my local phone book: my home phone number is not just listed for me but is also listed erroneously as the phone number for some family named Zirkind. (Yes, this is a true story.) Let me tell you—it’s annoying to receive phone calls and voicemail from people looking for the Zirkinds. For that matter, I’m sure the Zirkinds are also wondering why no one ever calls them. And when I call the Zirkinds to let them know about the error, my wife picks up the phone because I’ve called my own number. (Okay, that last part never happened.) If only the program that produced the phone book had used a set…

In any case, an array-based set is an array with one additional constraint of barring duplicates. While not allowing duplicates is a useful feature, this simple constraint also causes the set to have a different efficiency for one of the four primary operations.

Let’s analyze the reading, searching, insertion, and deletion operations in the context of an array-based set.

Reading from a set is exactly the same as reading from an array—it takes just one step for the computer to look up what’s contained within a particular index. As I described earlier, this is because the computer can jump to any index within the set since it can easily calculate and jump to its memory address.

Searching a set also turns out to be no different than searching an array—it takes up to N steps to search for a value within a set. And deletion is also identical between a set and an array—it takes up to N steps to delete a value and move data to the left to close the gap.

Insertion, however, is where arrays and sets diverge. Let’s first explore inserting a value at the end of a set, which was a best-case scenario for an array. We saw that with an array, the computer can insert a value at its end in a single step.

With a set, however, the computer first needs to determine that this value doesn’t already exist in this set—because that’s what sets do: they prevent duplicate data from being inserted into them.

Now, how will the computer ensure that the new data isn’t already contained in the set? Remember, a computer doesn’t know offhand what values are contained within the cells of an array or set. Because of this, the computer will first need to search the set to see whether the value we want to insert is already there. Only if the set does not yet contain our new value will the computer allow the insertion to take place.

So, every insertion into a set first requires a search.

Let’s see this in action with an example. Imagine our grocery list from earlier was stored as a set—which would be a decent choice since we don’t want to buy the same thing twice, after all. If our current set is ["apples", "bananas", "cucumbers", "dates", "elderberries"], and we want to insert "figs" into the set, the computer must execute the following steps, beginning with a search for "figs".

Step 1: Search index 0 for "figs":

It’s not there, but it might be somewhere else in the set. We need to make sure "figs" doesn’t exist anywhere before we can insert it.

Step 2: Search index 1:

Step 3: Search index 2:

Step 4: Search index 3:

Step 5: Search index 4:

Now that we’ve searched the entire set, we know with certainty that it doesn’t already contain "figs". At this point, it’s safe to complete the insertion. And that brings us to our final step:

Step 6: Insert "figs" at the end of the set:

Inserting a value at the end of a set is the best-case scenario, but we still had to perform six steps for a set originally containing five elements. That is, we had to search all five elements before performing the final insertion step.

Said another way: insertion into the end of a set will take up to N + 1 steps for N elements. This is because there are N steps of search to ensure that the value doesn’t already exist within the set, and then one step for the actual insertion. Contrast this with the regular array, in which such an insertion takes a grand total of one step.

In the worst-case scenario, where we’re inserting a value at the beginning of a set, the computer needs to search N cells to ensure that the set doesn’t already contain that value, another N steps to shift all the data to the right, and another final step to insert the new value. That’s a total of 2N + 1 steps. Contrast this to insertion into the beginning of a regular array, which only takes N + 1 steps.

Now, does this mean you should avoid sets just because insertion is slower for sets than regular arrays? Absolutely not. Sets are important when you need to ensure that there’s no duplicate data. (Hopefully, one day my phone book will be fixed.) But when you don’t have such a need, an array may be preferable, since insertions for arrays are more efficient than insertions for sets. You must analyze the needs of your own application and decide which data structure is a better fit.