Data Structures and Algorithms in Go: A Primer

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.

Types of Data Structures

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

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))
   }
}

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

123
456
789

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)
}

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

&{[ ]}
&{[ 1 ]}
&{[ 2, 1]}
&{[ 3, 2, 1]}

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)
}

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

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)
}

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

false
true

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)
}

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)

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

Comments

[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?

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

[MacBobby Chibuzor]

I will do that, thanks!