DEV Community

Cover image for Data Structures and Algorithms in Go: A Primer
MacBobby Chibuzor
MacBobby Chibuzor

Posted on

Data Structures and Algorithms in Go: A Primer

#go #algorithms #interview #tutorial

Introduction

Learning Data Structures and Algorithms is important for every developer regardless of whatever track you find yourself.

This article will teach you:

  • What Data Structures and Algorithms entails
  • Why you need to know how to write algorithms in your convenient language
  • Language choices
  • Types of data structures
  • Types of algorithms
  • Implementation methods and use cases of popular algorithms

A programmer is first of all a problem solver, and most computing problems can only be solved using algorithms. As such, knowledge of algorithms is imperative for all programmers. However, in recent times, the majority of developers starting out in tech without a formal Computer Science educational background skip this fundamentally important step.

You must have come across new developers writing powerful code for server side, working with frameworks, but do not know how algorithmic problem solving with that language they use. Chances are that, this applies to you also.

Why You Should Learn Algorithms

Coming across a puzzle or problem requires you to come up with and implement a fast and memory-efficient algorithm to solve it. Hands-on problem solving of programming challenges will help you actualize a better understanding of various algorithms and may even land you a job since many high-tech companies ask entry-level developers to solve programming challenges during job interviews and internship applications.

The algorithm you write to solve that problem will be checked automatically against many carefully selected tests to verify that it always produces a correct answer and fits into the time and memory constraints.

Language Choice

It doesn't really matter what programming language you're starting out with because it is language agnostic. There is a problem in front of you and it has no regard whatever tool you're using, as long as you solve it. However, many senior developers are conversant with writing algorithms in C++. Other popular languages include:

  • JavaScript
  • Python
  • C
  • Java

This does not mean that other languages cannot be used. For example, the codes in this article are written in Golang.

Data Structures

Data Structures refers to the way data is arranged or represented.

Image description

Types of Data Structures

There are lots of data structures but they can be classified under six categories as seen below.

Image description

1. Linear Data Structures

Under this category, lists, tuples and heaps are explained.

Lists

A list is a connected sequence of elements. It is similar to an array, but its normally easier to add or delete elements in a list.

In Go, lists are created from the container/list package, which has a PushBack method for appending elements. For example:

package main

import (
    "fmt"
    "container/list"
)
func main() {
  var newList list.List
  newList.PushBack(123)
  newList.PushBack(456)
  newList.PushBack(789)

  for element := newList.Front(); element != nil; element = element.Next() {
    fmt.Println(element.Value(int))
   }
}
Enter fullscreen mode Exit fullscreen mode

After running go filename.go the console should print the values of separate lines.

123
456
789
Enter fullscreen mode Exit fullscreen mode

Heaps

A heap is a data structure that can be expressed as a complete tree but is actually an array. To help your understanding, think of an array containing 11 elements. Now break this array into a binary heap such that it looks like a tree with one root on the top and two nodes branching from that root. Now treat these two nodes as roots, then branch out two sub nodes from them. A max heap has the biggest element in the array as the main root, while a min heap has the smallest element or key as the main root.

Heaps are mainly used in selection, graph, and k-way merge algorithms. Operations such as finding, merging, insertion, key changes, and deleting are performed on heaps. Heaps are part of the container/heap package in Go.

The code below seeks to explain insertion and extraction in Go:

package main
import "fmt"

type MaxHeap struct {
  arr []int
}
func (hp *MaxHeap) Insert (key int){
   hp.arr = append(hp.arr, key)
   hp.heapifyMaxUp(len(hp.arr) - 1)
}
func (hp *MaxHeap) heapifyMaxUp (index int) {
   for hp.arr[parent(index)] < hp.arr[index] {
   hp.swap(parent(index), index)
   index = parent(index)
}
func parent(i int) int{
   return (i - 1)/2
}
func left(i int) int{
   return 2*i + 2
}
func right(i int) int{
   return 2*i + 2
}
func (hp *MaxHeap) swap(int1, int2 int) {
  hp.arr[int1], hp.arr[int2] = hp.arr[int2], hp.arr[int1]
}

func main() {
  m := &MaxHeap
  fmt.Println(m)

  makeHeap := []int(1,2,3)
  for _, v := range makeHeap {
     m.Insert(v)
}
Enter fullscreen mode Exit fullscreen mode

The console prints out three lines, each an update of the array:

&{[ ]}
&{[ 1 ]}
&{[ 2, 1]}
&{[ 3, 2, 1]}
Enter fullscreen mode Exit fullscreen mode

This is an example of a max heap in Go where the algorithm updates each new iteration by putting biggest numbers first.

Tuples

A tuple is a finite sorted list of elements. It is a data structure that groups data. For example, let's find the exponential of an integer and then return it as a tuple:

package main
import (
    "fmt"
)
func exponents(x, int) (int, int) {
   return x*x, x*x*x
}
func main() {
   var square int
   var cube int
   square, cube = exponents(10)
   fmt.Println("Square of 10 is", square)
   fmt.Println("Cube of 10 is", cube)
}
Enter fullscreen mode Exit fullscreen mode

After running go filename.go the results are going to print the following in the console:

Square of 10 is 100
Cube of 10 is 1000
Enter fullscreen mode Exit fullscreen mode

Algorithms

An algorithm is any well-defined computational procedure which accepts value(s) as input and produces value(s) as output. In essence, it is a sequence of computational steps that transform the input into the output.

To explain how algorithms are written using day to day terms, let's assume you were building a SaaS.

  1. You come up with the whole idea
  2. You get the UI Design to clearly portray the idea. Does the UI portray everything?
    1. Yes. Move to step 3
    2. No. Repeat step 2
  3. You build the frontend.
  4. Next, the Backend is built to serve the static assets.

  5. Next, write unit tests.

    1. Everything works well? Move to step 6.
    2. There's a problem? Debug.
      1. Debugging successful? Repeat step 5
      2. Debugging not successful? Repeat 5b.

  6. Deploy to production.

  7. Maintain

In simpler terms, you should understand algorithms to be computational procedures in solving a problem. It is also important for algorithms to not be falsifiable when analysed for any case. Algorithmic analysis is represented generally in three cases:

  • Best Case - where the algorithm takes the shortest time and runs the fastest.
  • Worst Case - where the algorithm takes the longest time and runs the slowest.
  • Average Case - where random input is used to predict the algorithm's run-time

Types of Algorithms with Examples

Brute Force Algorithms

Brute Force algorithms widely used because they easily solve complex problems. Searching, string matching, and matrix multiplication are some of their strengths. Single computational tasks can be solved using brute force algorithms also.

Example code:

package main

import (
    "fmt"
)
//findElement method given array and k element
func findElement(arr[10] int, k int) bool {
    var i int
    for i=0; i< 10; i++ {
        if arr[i]==k {
            return true
        }
    }
    return false
}
// main method
func main() {
    var arr = [10]int{1,4,7,8,3,9,2,4,1,8}
    var check bool = findElement(arr,10)
    fmt.Println(check)
    var check2 bool = findElement(arr,9)
    fmt.Println(check2)
}
Enter fullscreen mode Exit fullscreen mode

Running go filename.go gives the following results in the console:

false
true
Enter fullscreen mode Exit fullscreen mode

There are classical algorithms in every programming language. To save time, we are going to treat a limited number of examples. These include:

  • Sorting
    • Bubble
    • Selection
    • Insertion
    • Shell
    • Merge
    • Quick
  • Searching
    • Linear
    • Sequential
    • Binary
    • Interpolation
  • Recursion
  • Hashing

Sorting

Sorting algorithms arrange the elements in a collection in ascending or descending order.

Bubble Sort

The bubble sort algorithm is a sorting algorithm that compares a pair of neighboring elements and swaps them if they are in the wrong order.

In example code:

package main
// importing fmt and bytes package
import (
  "fmt")
//bubble Sorter method
func bubbleSorter(integers [11]int) {
  var num int  num = 11  
  var isSwapped bool
  isSwapped = true
  for isSwapped {
    isSwapped = false
    var i int
    for i = 1; i < num; i++ {
      if integers[i-1] > integers[i] {
        var temp = integers[i]
        integers[i] = integers[i-1]
        integers[i-1] = temp
        isSwapped = true
      }
    }
  }
  fmt.Println(integers)
}
// main method
func main() {
  var integers [11]int = [11]int{31, 13, 12, 4, 18, 16, 7, 2, 3, 0, 10}
  fmt.Println("Bubble Sorter")
  bubbleSorter(integers)
}
Enter fullscreen mode Exit fullscreen mode

The bubbleSorter function takes an integer array and then sorts the elements into ascending order.
Running go filename.go gives the result:

Bubble Sorter
( 0 2 3 4 7 10 12 13 16 18 31)
Enter fullscreen mode Exit fullscreen mode

Where To Go From Here

Now that you have understood what data structures and algorithms are, it's importance to programmers in solving problems, some of the types of data structures and algorithms, examples in Go, the best next step is to keep learning how to apply other data structures and algorithms in solving puzzles as regularly as possible.

Next you should start implementing algorithms in whatever codebase you think it'd fit perfectly.

Learning algorithms without implementing them is like learning surgery based solely on reading an anatomy book - Alexander Kulikov

Furthermore, you should be more confident of your next technical assessment!

I am MacBobby Chibuzor, a contract Technical Writer at Wevolver and Golang Developer. Follow me for more articles related to Golang, Machine Learning, IoT, Data Structures and Algorithms, Web Development and Security Testing

Top comments (3)

Collapse
 
b0r profile image
b0r •

Hi MacBobby,

thank you for the nice post about data structures and algorithms in Go!!

May I just ask you to use this syntax for code blocks that adds code highlighting, so it's easier to read. Please?

Image description

Source:
support.codebasehq.com/articles/ti...

Collapse
 
theghostmac profile image
MacBobby Chibuzor •

I will do that, thanks!

Collapse
 
suely_sampaioboccanera_e profile image
Suely Sampaio Boccanera •

Hi MacBobby,

Thank you for the posts, they helps a lot.
I would like comment that are few errors in the Heap example.
I changed the code and ran it on Go Playground.
The code was shown below with the output.

package main

import "fmt"

type MaxHeap struct {
arr []int
}

func (hp *MaxHeap) Insert(key int) {
hp.arr = append(hp.arr, key)
hp.heapifyMaxUp(len(hp.arr) - 1)
}

func (hp *MaxHeap) heapifyMaxUp(index int) {
for hp.arr[parent(index)] < hp.arr[index] {
hp.swap(parent(index), index)
index = parent(index)
}
}

func parent(i int) int {
return (i - 1) / 2
}

func left(i int) int {
return 2*i + 2
}

func right(i int) int {
return 2*i + 2
}

func (hp *MaxHeap) swap(int1, int2 int) {
hp.arr[int1], hp.arr[int2] = hp.arr[int2], hp.arr[int1]
}

func main() {
var m *MaxHeap
m = new(MaxHeap)
fmt.Println(m)

makeHeap := []int{1, 2, 3}
for _, v := range makeHeap {
    m.Insert(v)
    fmt.Println(m)
}
Enter fullscreen mode Exit fullscreen mode

}

Output:
&{[]}
&{[1]}
&{[2 1]}
&{[3 1 2]}

Read next

mshsayket profile image

How to Generate QR Code in Laravel 11

Saddam Hossain -

radchenko profile image

Practical Experience: Integrating Over 50 Neural Networks Into One Open-Source Project

Vladislav Radchenko -

truongpx396 profile image

πŸ” Solidity Limitations, Solutions, Best Practices and Gas Optimization πŸš€

Truong Phung -

mdarifulhaque profile image

2563. Count the Number of Fair Pairs

MD ARIFUL HAQUE -