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.
- You come up with the whole idea
- You get the UI Design to clearly portray the idea. Does the UI portray everything?
- Yes. Move to step 3
- No. Repeat step 2
- You build the frontend.
- Next, the Backend is built to serve the static assets.
-
Next, write unit tests.
- Everything works well? Move to step 6.
- There's a problem? Debug.
- Debugging successful? Repeat step 5
- Debugging not successful? Repeat 5b.
Deploy to production.
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
Top comments (3)
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...
I will do that, thanks!
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)
}
Output:
&{[]}
&{[1]}
&{[2 1]}
&{[3 1 2]}