Learn Data Structures and Algorithms with Golang

Level up your Go programming skills to develop faster and more efficient code

Bhagvan Kommadi

• Publisher: Packt Publishing
• Year: 2019
• ISBN:
  9781789618419
• Edition: 1
• Topic: Informatica
• Subtopic: Informatica generale

Explore Golang's data structures and algorithms to design, implement, and analyze code in the professional setting

Key Features

• Learn the basics of data structures and algorithms and implement them efficiently
• Use data structures such as arrays, stacks, trees, lists and graphs in real-world scenarios
• Compare the complexity of different algorithms and data structures for improved code performance

Book Description

Golang is one of the fastest growing programming languages in the software industry. Its speed, simplicity, and reliability make it the perfect choice for building robust applications. This brings the need to have a solid foundation in data structures and algorithms with Go so as to build scalable applications. Complete with hands-on tutorials, this book will guide you in using the best data structures and algorithms for problem solving.

The book begins with an introduction to Go data structures and algorithms. You'll learn how to store data using linked lists, arrays, stacks, and queues. Moving ahead, you'll discover how to implement sorting and searching algorithms, followed by binary search trees. This book will also help you improve the performance of your applications by stringing data types and implementing hash structures in algorithm design. Finally, you'll be able to apply traditional data structures to solve real-world problems.

By the end of the book, you'll have become adept at implementing classic data structures and algorithms in Go, propelling you to become a confident Go programmer.

What you will learn

• Improve application performance using the most suitable data structure and algorithm
• Explore the wide range of classic algorithms such as recursion and hashing algorithms
• Work with algorithms such as garbage collection for efficient memory management
• Analyze the cost and benefit trade-off to identify algorithms and data structures for problem solving
• Explore techniques for writing pseudocode algorithm and ace whiteboard coding in interviews
• Discover the pitfalls in selecting data structures and algorithms by predicting their speed and efficiency

Who this book is for

This book is for developers who want to understand how to select the best data structures and algorithms that will help solve coding problems. Basic Go programming experience will be an added advantage.

Section 1: Introduction to Data Structures and Algorithms and the Go Language

We will be introducing the abstract data types, definition, and classification of data structures. Readers will be well-versed with performance analysis of algorithms and choosing appropriate data structures for structural design patterns after reading this part.

This section contains the following chapters:

• Chapter 1, Data Structures and Algorithms
• Chapter 2, Getting Started with Go for Data Structures and Algorithms

Data Structures and Algorithms

A data structure is the organization of data to reduce the storage space used and to reduce the difficulty while performing different tasks. Data structures are used to handle and work with large amounts of data in various fields, such as database management and internet indexing services.

In this chapter, we will focus on the definition of abstract datatypes, classifying data structures into linear, nonlinear, homogeneous, heterogeneous, and dynamic types. Abstract datatypes, such as Container, List, Set, Map, Graph, Stack, and Queue, are presented in this chapter. We will also cover the performance analysis of data structures, choosing the right data structures, and structural design patterns.

The reader can start writing basic algorithms using the right data structures in Go. Given a problem, choosing the data structure and different algorithms will be the first step. After this, doing performance analysis is the next step. Time and space analysis for different algorithms helps compare them and helps you choose the optimal one. It is essential to have basic knowledge of Go to get started.

In this chapter, we will cover the following topics:

• Classification of data structures and structural design patterns
• Representation of algorithms
• Complexity and performance analysis
• Brute force algorithms
• Divide and conquer algorithms
• Backtracking algorithms

Technical requirements

Install Go version 1.10 from https://golang.org/doc/install for your operating system.

The code files for this chapter can be found at the following GitHub URL: https://github.com/PacktPublishing/Learn-Data-Structures-and-Algorithms-with-Golang/tree/master/Chapter01.

Check the installation of Go by running the hello world program at https://github.com/PacktPublishing/Learn-Data-Structures-and-Algorithms-with-Golang/tree/master/hello_world:

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main

// importing fmt package
import (
 "fmt"
)
// main method
func main() {
 fmt.Println("Hello World")
}

Run the following commands:

go build
./hello_world

The following screenshot displays the output:

Let's take a look at the classification of data structures and structural design patterns in the next section.

Classification of data structures and structural design patterns

You can choose a data structure by using classification. In this section, we discuss data structure classification in detail. The design patterns related to the data structure are covered after the classification.

In the next section, we'll take a look at classification of data structures.

Classification of data structures

The term data structure refers to the organization of data in a computer's memory, in order to retrieve it quickly for processing. It is a scheme for data organization to decouple the functional definition of a data structure from its implementation. A data structure is chosen based on the problem type and the operations performed on the data.

If the situation requires various datatypes within a data structure, we can choose heterogeneous data structures. Linked, ordered, and unordered lists are grouped as heterogeneous data structures. Linear data structures are lists, sets, tuples, queues, stacks, and heaps. Trees, tables, and containers are categorized as nonlinear data structures. Two-dimensional and multidimensional arrays are grouped as homogeneous data structures. Dynamic data structures are dictionaries, tree sets, and sequences.

The classification of Data Structures is show in the following diagram:

Let's take a look at lists, tuples and heaps in the next sections.

Lists

A list is a sequence of elements. Each element can be connected to another with a link in a forward or backward direction. The element can have other payload properties. This data structure is a basic type of container. Lists have a variable length and developer can remove or add elements more easily than an array. Data items within a list need not be contiguous in memory or on disk. Linked lists were proposed by Allen Newell, Cliff Shaw, and Herbert A. Simon at RAND Corporation.

To get started, a list can be used in Go, as shown in the following example; elements are added through the PushBack method on the list, which is in the container/list package:

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main

// importing fmt and container list packages
import (
 "fmt"
 "container/list")

// main method
func main() {
 var intList list.List
 intList.PushBack(11)
 intList.PushBack(23)
 intList.PushBack(34)

 for element := intList.Front(); element != nil; element=element.Next() {
 fmt.Println(element.Value.(int))
 }
}

The list is iterated through the for loop, and the element's value is accessed through the Value method.

Run the following command...