Implementing a Singly Linked List in Go

In this video, we’ll be taking forward the concepts we covered in the last video and looking at how we can implement a singly linked list in Go!

Implementation

Much like all of the other data structures we’ve covered so far, we’ll be creating a struct that will house our implementation:

type LinkedList struct {
}

We’ll also want to create a Node struct which will contain the definition of nodes within our linked list:

type Node struct {
  Value string
  Next *Node
}

We’ll be storing string values within this particular linked list implementation.

With this new Node struct defined, we can then update our empty LinkedList struct so that it has a pointer to the first Node in our linked list, otherwise known as the Head.

We also want to add a Size field which will keep an updated count as to how many Nodes are present within our Linked List:

type LinkedList struct {
  Head *Node
  Size int
}

Adding Elements To our Linked List

We now have the foundation built for our Linked List, it’s time to extend this and start building the methods that will allow us to perform actions on our Linked List.

The first one we’ll be tackling is the Insert method which will all us to add a new Node to the start of our Linked List.

func (l *LinkedList) Insert(elem string) {
  node := Node{
    Next: l.Head,
    Value: elem,
  }
  l.Head = node
  l.Size++
}

Note - We are adding new elements to the front of our the linked list by updating the Head. This means that when we go to read through our Linked List, we’ll be doing it in a Last-In-First-Out order.

Awesome, we now have a method that will allow us to insert new elements to the head of our Linked List!

Deleting The First Element From our Linked List

Let’s now have a look at implementing the converse delete method that will allow us to remove the first element from our Linked List:

func (l *LinkedList) DeleteFirst() {
  l.Head = l.Head.Next
  l.Size--
}

Listing Elements in our Linked List

We have the ability to both add and remove elements from our linked list at this point, now we want to view the elements of our linked list and for that we need to implement the List method.

This method will set the current node to the Head of our linked list, then it will iterate through each element retrieving the next element as well as printing out the current element until it reaches the end:

func (l *LinkedList) List() {
  current := l.Head
  for current != nil {
    fmt.Println("%+v\n", current)
    current = current.Next
  }
}

Searching for Elements in our Linked List

At this point, we have the ability to list out our linked list, but what if we wanted to search for an element and see if it exists?

We can take our List implementation a step further and define a Search method that will check each time it visits a node whether or not the value is equal to what we are searching for:

func (l *LinkedList) Search(elem string) *Node {
  current := l.Head
  for current != nil {
    if current.Value = elem {
      return current
    }
    current = current.Next
  }
  return nil
}

Deleting Elements From our Linked List

If we have the ability to find an element from our linked list, we then need just a little bit extra logic thrown in there to delete an element that we find.

This is slightly trickier though, we need to keep a reference to the previous element as we are looping through our list. If the current node is the one we want to delete then we have to update the previous element to point to the current node’s next node, effectively removing the current node from our list.

func (l *LinkedList) Delete(elem string) {
  previous := l.Head
  current := l.Head
  for current != nil {
    if current.Value == elem {
      previous.Next = current.Next
    }
    previous = current
    current = current.Next
  }
}

Getting the Size of our Linked List

We can return the size of our linked list fairly easily, at this point most of the work has been done for us as we are constantly updating the Size field of our LinkedList whenever we add or remove an item from it.

// Size - returns the size of our linked list
func (l *LinkedList) Size() {
  return l.Size
}

Quiz

Try your hand at these questions to help cement the concepts we covered in these past few videos: