Implementing a Set in Go

👋 Hey Gophers, in this video, we are going to be looking at how we can implement the Set data structure in Go.

Set Implementation

Let’s kick this off by creating a struct that we will base our Set implementation on:

type Set struct {
  Elements map[string]struct{}
}

Given we are working with a map, we’ll have to have a mechanism for instantiating this map. Let’s create a New function now that will return a Set that is ready to use:

func NewSet() *Set {
  var set Set
  set.Elements = make(map[string]struct{})
  return &set
}

Cool, we now have a set that is ready to use!

Add

Let’s start off by tackling the Add method which will have the responsibility of adding a new element to the set:

func (s *Set) Add(elem string) {
  s.Elements[elem] = struct{}{}
}

Awesome, we now have a means for adding elements to the set. No matter how many times we try and add the same string element to our Set, it will only be registered once within our Set implementation.

Note - Using an empty struct here allows us to reduce the memory our set uses. We could in theory use a bool, but then more memory is allocated when it is not necessary.

Delete

Next, we’ll want to implement the method that will allow us to remove an element that we’ve just added to our Set:

func (s *Set) Delete(elem string) error {
  if _, exists := s.Elements[elem]; !exists {
    return errors.New("element does not exist")
  }
  delete(s.Elements, elem)
  return nil
}

Perfect, we now have the ability to both add and remove elements from our Set, we now just need to implement some of the helper methods that will allow us to do things like list out our set and check if an item exists within the set.

Contains

Let’s now implement a method that will allow us to check if a value already exists within a Set:

// Contains - checks to see if an element exists within the set
func (s *Set) Contains(elem string) bool {
	_, exists := s.Elements[elem]
	return exists
}

List

Finally, let’s have a look at how we can implement the List method which will list out all of the items within our Set.

func (s *Set) List() {
  for k,_ := range s.Elements {
    fmt.Println(k)
  }
}

Quiz

Let’s take a second to validate some of the concepts we’ve learned within these last 2 lessons. Try your hand at actively recalling the answers to these questions: