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
Â
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.
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.
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.
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 commands:
go run list.go
The following screenshot displays the output:

Let's take a look at Tuples in the next section.
A tuple is a finite sorted list of elements. It is a data structure that groups data. Tuples are typically immutable sequential collections. The element has related fields of different datatypes. The only way to modify a tuple is to change the fields. Operators such as + and * can be applied to tuples. A database record is referred to as a tuple. In the following example, power series of integers are calculated and the square and cube of the integer is returned as a tuple:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) //gets the power series of integer a and returns tuple of square of a // and cube of a func powerSeries(a int) (int,int) { return a*a, a*a*a }
The main
method calls the powerSeries
method with 3
as a parameter. Thesquare
and cube
 values are returned from the method:
// main method func main() { var square int var cube int square, cube = powerSeries(3) fmt.Println("Square ", square, "Cube", cube) }
Â
Â
Â
Â
Run the following commands:
go run tuples.go
The following screenshot displays the output:

The tuples can be named in the powerSeries
function, as shown in the following code:
func powerSeries(a int) (square int, cube int) { square = a*a cube = square*a return }
If there is an error, it can be passed with tuples, as shown in the following code:
func powerSeries(a int) (int, int, error) { square = a*a cube = square*a return square,cube,nil }
A heap is a data structure that is based on the heap
property. The heap data structure is 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. According to the heap order (maximum heap) property, the value stored at each node is greater than or equal to its children.
If the order is descending, it is referred to as a maximum heap; otherwise, it's a minimum heap. The heap data structure was proposed by J.W.J. Williams in 1964 for a heap sorting algorithm. It is not a sorted data structure, but partially ordered. The following example shows how to use the container/heap
package to create a heap data structure:
//main package has examples shown //in Hands-On Data Structures and algorithms with Go book package main // importing fmt package and container/heap import ( "container/heap" "fmt" ) // integerHeap a type type IntegerHeap []int // IntegerHeap method - gets the length of integerHeap func (iheap IntegerHeap) Len() int { return len(iheap) } // IntegerHeap method - checks if element of i index is less than j index func (iheap IntegerHeap) Less(i, j int) bool { return iheap[i] < iheap[j] } // IntegerHeap method -swaps the element of i to j index func (iheap IntegerHeap) Swap(i, j int) { iheap[i], iheap[j] = iheap[j], iheap[i] }
IntegerHeap
has a Push
method that pushes the item with the interface:
//IntegerHeap method -pushes the item func (iheap *IntegerHeap) Push(heapintf interface{}) { *iheap = append(*iheap, heapintf.(int)) } //IntegerHeap method -pops the item from the heap func (iheap *IntegerHeap) Pop() interface{} { var n int var x1 int var previous IntegerHeap = *iheap n = len(previous) x1 = previous[n-1] *iheap = previous[0 : n-1] return x1 } // main method func main() { var intHeap *IntegerHeap = &IntegerHeap{1,4,5} heap.Init(intHeap) heap.Push(intHeap, 2) fmt.Printf("minimum: %d\n", (*intHeap)[0]) for intHeap.Len() > 0 { fmt.Printf("%d \n", heap.Pop(intHeap)) } }
Run the following commands:
go run heap.go
The following screenshot displays the output:

Let's take a look at structural design patterns in the next section
Structural design patterns describe the relationships between the entities. They are used to form large structures using classes and objects. These patterns are used to create a system with different system blocks in a flexible manner. Adapter, bridge, composite, decorator, facade, flyweight, private class data, and proxy are the Gang of Four (GoF) structural design patterns. The private class data design pattern is the other design pattern covered in this section.
We will take a look at adapter and bridge design patterns in the next sections.
Â
The adapter pattern provides a wrapper with an interface required by the API client to link incompatible types and act as a translator between the two types. The adapter uses the interface of a class to be a class with another compatible interface. When requirements change, there are scenarios where class functionality needs to be changed because of incompatible interfaces.
The dependency inversion principle can be adhered to by using the adapter pattern, when a class defines its own interface to the next level module interface implemented by an adapter
class. Delegation is the other principle used by the adapter pattern. Multiple formats handling source-to-destination transformations are the scenarios where the adapter pattern is applied.
The adapter pattern comprises the target, adaptee, adapter, and client:
- Target is the interface that the client calls and invokes methods on the adapter and adaptee.
- The client wants the incompatible interface implemented by the adapter.
- The adapter translates the incompatible interface of the adaptee into an interface that the client wants.
Let's say you have an IProcessor
 interface with a process
method, the Adapter
 class implements the process
 method and has an Adaptee
 instance as an attribute. The Adaptee
class has a convert
 method and an adapterType
 instance variable. The developer while using the API client calls the process
 interface method to invoke convert
on Adaptee
. The code is as follows:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) //IProcess interface type IProcess interface { process() } //Adapter struct type Adapter struct { adaptee Adaptee }
Â
Â
Â
Â
Â
Â
The Adapter
class has a process
 method that invokes the convert
method on adaptee
:
//Adapter class method process func (adapter Adapter) process() { fmt.Println("Adapter process") adapter.adaptee.convert() } //Adaptee Struct type Adaptee struct { adapterType int } // Adaptee class method convert func (adaptee Adaptee) convert() { fmt.Println("Adaptee convert method") } // main method func main() { var processor IProcess = Adapter{} processor.process() }
Run the following commands:
go run adapter.go
The following screenshot displays the output:

Let's take a look at Bridge pattern in the next section.
Bridge decouples the implementation from the abstraction. The abstract base class can be subclassed to provide different implementations and allow implementation details to be modified easily. The interface, which is a bridge, helps in making the functionality of concrete classes independent from the interface implementer classes. The bridge patterns allow the implementation details to change at runtime.
Â
The bridge pattern demonstrates the principle, preferring composition over inheritance. It helps in situations where one should subclass multiple times orthogonal to each other. Runtime binding of the application, mapping of orthogonal class hierarchies, and platform independence implementation are the scenarios where the bridge pattern can be applied.
The bridge pattern components are abstraction, refined abstraction, implementer, and concrete implementer. Abstraction is the interface implemented as an abstract class that clients invoke with the method on the concrete implementer. Abstraction maintains a has-a relationship with the implementation, instead of an is-a relationship. The has-a relationship is maintained by composition. Abstraction has a reference of the implementation. Refined abstraction provides more variations than abstraction.
Let's sayIDrawShape
is an interface with the drawShape
 method.  DrawShape
implements the IDrawShape
interface. We create an IContour
bridge interface with the drawContour
 method. The contour class implements the IContour
interface. The ellipse
class will have a, b , r properties and drawShape
(an instance of DrawShape
). The ellipse
class implements the contour
 bridge interface to implement the drawContour
 method. The  drawContour
 method calls the drawShape
 method on the drawShape
 instance.
The following code demonstrates the bridge implementation:Â
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) //IDrawShape interface type IDrawShape interface { drawShape(x[5] float32,y[5] float32) } //DrawShape struct type DrawShape struct{}
The drawShape
method draws the shape given the coordinates, as shown in the following code:
// DrawShape struct has method draw Shape with float x and y coordinates func (drawShape DrawShape) drawShape(x[5] float32, y[5] float32) { fmt.Println("Drawing Shape") } //IContour interace type IContour interface { drawContour(x[5] float32 ,y[5] float32) resizeByFactor(factor int) } //DrawContour struct type DrawContour struct { x[5] float32 y[5] float32 shape DrawShape factor int }
The drawContour
method of the DrawContour
 classcalls the drawShape
 method on the shape
instance, this is shown in the following code:
//DrawContour method drawContour given the coordinates func (contour DrawContour) drawContour(x[5] float32,y[5] float32) { fmt.Println("Drawing Contour") contour.shape.drawShape(contour.x,contour.y) } //DrawContour method resizeByFactor given factor func (contour DrawContour) resizeByFactor(factor int) { contour.factor = factor } // main method func main() { var x = [5]float32{1,2,3,4,5} var y = [5]float32{1,2,3,4,5} var contour IContour = DrawContour{x,y,DrawShape{},2} contour.drawContour(x,y) contour.resizeByFactor(2) }
Run the following commands:
go run bridge.go
Â
The following screenshot displays the output:

We will take a look at Composite, Decorator, Facade and Flyweight design patterns in the next sections.
A composite is a group of similar objects in a single object. Objects are stored in a tree form to persist the whole hierarchy. The composite pattern is used to change a hierarchical collection of objects. The composite pattern is modeled on a heterogeneous collection. New types of objects can be added without changing the interface and the client code. You can use the composite pattern, for example, for UI layouts on the web, for directory trees, and for managing employees across departments. The pattern provides a mechanism to access the individual objects and groups in a similar manner.
The composite pattern comprises the component
interface, component
class, composite, and client:
- The
component
interface defines the default behavior of all objects and behaviors for accessing the components of the composite. - The
composite
andcomponent
classes implement thecomponent
interface. - The client interacts with the component interface to invoke methods in the composite.
Let's say there is an IComposite
 interface with the perform
method and BranchClass
 that implements IComposite
 and has the addLeaf
, addBranch
, and perform
 methods. The Leaflet
class implements IComposite
with the perform
method. BranchClass
has a one-to-many relationship with leafs
and branches
. Iterating over the branch recursively, one can traverse the composite tree, as shown in the following code:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) // IComposite interface type IComposite interface { perform() } // Leaflet struct type Leaflet struct { name string } // Leaflet class method perform func (leaf *Leaflet) perform() { fmt.Println("Leaflet " + leaf.name) } // Branch struct type Branch struct { leafs []Leaflet name string branches[]Branch }
The perform
method of the Branch
 class calls the perform
 method on branch
and leafs
, as seen in the code:
// Branch class method perform func (branch *Branch) perform() { fmt.Println("Branch: " + branch.name) for _, leaf := range branch.leafs { leaf.perform() } for _, branch := range branch.branches { branch.perform() } } // Branch class method add leaflet func (branch *Branch) add(leaf Leaflet) { branch.leafs = append(branch.leafs, leaf) }
As shown in the following code, the addBranch
method of the Branch
 class adds a new branch
:
//Branch class method addBranch branch func (branch *Branch) addBranch(newBranch Branch) { branch.branches = append(branch.branches,newBranch) } //Branch class method getLeaflets func (branch *Branch) getLeaflets() []Leaflet { return branch.leafs } // main method func main() { var branch = &Branch{name:"branch 1"} var leaf1 = Leaflet{name:"leaf 1"} var leaf2 = Leaflet{name:"leaf 2"} var branch2 = Branch{name:"branch 2"} branch.add(leaf1) branch.add(leaf2) branch.addBranch(branch2) branch.perform() }
Run the following commands:
go run composite.go
The following screenshot displays the output:

Let's take a look at Decorator pattern in the next section.
In a scenario where class responsibilities are removed or added, the decorator pattern is applied. The decorator pattern helps with subclassing when modifying functionality, instead of static inheritance. An object can have multiple decorators and run-time decorators. The single responsibility principle can be achieved using a decorator. The decorator can be applied to window components and graphical object modeling. The decorator pattern helps with modifying existing instance attributes and adding new methods at run-time.
Â
The decorator pattern participants are the component interface, the concrete component class, and the decorator
class:
Let 's sayIProcess
is an interface with the process
method. ProcessClass
implements an interface with the process
method. ProcessDecorator
implements the process interface and has an instance of ProcessClass
. ProcessDecorator
can add more functionality than ProcessClass
, as shown in the following code:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) // IProcess Interface type IProcess interface { process() } //ProcessClass struct type ProcessClass struct{} //ProcessClass method process func (process *ProcessClass) process() { fmt.Println("ProcessClass process") } //ProcessDecorator struct type ProcessDecorator struct { processInstance *ProcessClass }
In the following code, the ProcessDecorator
class process
method invokes the process
method on the decorator instance of ProcessClass
:
//ProcessDecorator class method process func (decorator *ProcessDecorator) process() { if decorator.processInstance == nil { fmt.Println("ProcessDecorator process") } else { fmt.Printf("ProcessDecorator process and ") decorator.processInstance.process() } } //main method func main() { var process = &ProcessClass{} var decorator = &ProcessDecorator{} decorator.process() decorator.processInstance = process decorator.process() }
Run the following commands:
go run decorator.go
The following screenshot displays the output:

Let's take a look at Facade pattern in the next section.
Facade is used to abstract subsystem interfaces with a helper. The facade design pattern is used in scenarios when the number of interfaces increases and the system gets complicated. Facade is an entry point to different subsystems, and it simplifies the dependencies between the systems. The facade pattern provides an interface that hides the implementation details of the hidden code.
A loosely coupled principle can be realized with a facade pattern. You can use a facade to improve poorly designed APIs. In SOA, a service facade can be used to incorporate changes to the contract and implementation.
Â
The facade pattern is made up of the facade
class, module classes, and a client:
- The facade delegates the requests from the client to the module classes. The
facade
class hides the complexities of the subsystem logic and rules. - Module classes implement the behaviors and functionalities of the module subsystem.
- The client invokes the
facade
method. Thefacade
class functionality can be spread across multiple packages and assemblies.
For example, account, customer, and transaction are the classes that have account, customer, and transaction creation methods. BranchManagerFacade
can be used by the client to create an account, customer, and transaction:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) //Account struct type Account struct{ id string accountType string } //Account class method create - creates account given AccountType func (account *Account) create(accountType string) *Account{ fmt.Println("account creation with type") account.accountType = accountType return account } //Account class method getById given id string func (account *Account) getById(id string) *Account { fmt.Println("getting account by Id") return account }
The account
class has the deleteById
 method, which is used to delete an account with a given ID, as shown in the following code:
//Account class method deleteById given id string func (account *Account) deleteById(id string)() { fmt.Println("delete account by id") } //Customer struct type Customer struct{ name string id int }
In the following code, the customer
class has a method that creates a new customer with name
:
//Customer class method create - create Customer given name func (customer *Customer) create(name string) *Customer { fmt.Println("creating customer") customer.name = name return customer } //Transaction struct type Transaction struct{ id string amount float32 srcAccountId string destAccountId string }
As shown in the following code, the transaction
class has the create
 method for creating a transaction:
//Transaction class method create Transaction func (transaction *Transaction) create(srcAccountId string, destAccountId string,amount float32) *Transaction { fmt.Println("creating transaction") transaction.srcAccountId = srcAccountId transaction.destAccountId = destAccountId transaction.amount = amount return transaction } //BranchManagerFacade struct type BranchManagerFacade struct { account *Account customer *Customer transaction *Transaction } //method NewBranchManagerFacade func NewBranchManagerFacade() *BranchManagerFacade { return &BranchManagerFacade{ &Account{}, &Customer{}, &Transaction{}} }
Â
Â
Â
Â
BranchManagerFacade
has the createCustomerAccount
 method, which calls the create
method on the customer
class instance, as shown in the following code:
//BranchManagerFacade class method createCustomerAccount func (facade *BranchManagerFacade) createCustomerAccount(customerName string, accountType string) (*Customer,*Account) { var customer = facade.customer.create(customerName) var account = facade.account.create(accountType) return customer, account } //BranchManagerFacade class method createTransaction func (facade *BranchManagerFacade) createTransaction(srcAccountId string, destAccountId string, amount float32) *Transaction { var transaction = facade.transaction.create(srcAccountId,destAccountId,amount) return transaction }
The main
method calls the NewBranchManagerFacade
method to create a facade. The methods on facade
are invoked to create customer
and account
:
//main method func main() { var facade = NewBranchManagerFacade() var customer *Customer var account *Account customer, account = facade.createCustomerAccount("Thomas Smith", "Savings") fmt.Println(customer.name) fmt.Println(account.accountType) var transaction = facade.createTransaction("21456","87345",1000) fmt.Println(transaction.amount) }
go run facade.go
The following screenshot displays the output:

Â
Â
Let's take a look at Flyweight pattern in the next section.
Flyweight is used to manage the state of an object with high variation. The pattern allows us to share common parts of the object state among multiple objects, instead of each object storing it. Variable object data is referred to as extrinsic state, and the rest of the object state is intrinsic. Extrinsic data is passed to flyweight methods and will never be stored within it. Flyweight pattern helps reduce the overall memory usage and the object initializing overhead. The pattern helps create interclass relationships and lower memory to a manageable level.
Flyweight objects are immutable. Value objects are a good example of the flyweight pattern. Flyweight objects can be created in a single thread mode, ensuring one instance per value. In a concurrent thread scenario, multiple instances are created. This is based on the equality criterion of flyweight objects.
The participants of the flyweight pattern are the FlyWeight
interface, ConcreteFlyWeight
, FlyWeightFactory
, and the Client
classes:
- The
FlyWeight
interface has a method through which flyweights can get and act on the extrinsic state. ConcreteFlyWeight
implements theFlyWeight
interface to represent flyweight objects.FlyweightFactory
is used to create and manage flyweight objects. The client invokesFlyweightFactory
to get a flyweight object.UnsharedFlyWeight
can have a functionality that is not shared.Client
classes
Let's sayDataTransferObject
is an interface with the getId
method. DataTransferObjectFactory
creates a data transfer object through getDataTransferObject
by the DTO
type. The DTO
types are customer, employee, manager, and address, as shown in the following code:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) //DataTransferObjectFactory struct type DataTransferObjectFactory struct { pool map[string] DataTransferObject } //DataTransferObjectFactory class method getDataTransferObject func (factory DataTransferObjectFactory) getDataTransferObject(dtoType string) DataTransferObject { var dto = factory.pool[dtoType] if dto == nil { fmt.Println("new DTO of dtoType: " + dtoType) switch dtoType{ case "customer": factory.pool[dtoType] = Customer{id:"1"} case "employee": factory.pool[dtoType] = Employee{id:"2"} case "manager": factory.pool[dtoType] = Manager{id:"3"} case "address": factory.pool[dtoType] = Address{id:"4"} } dto = factory.pool[dtoType] } return dto }
In the following code, the DataTransferObject
interface is implemented by the Customer
class:
// DataTransferObject interface type DataTransferObject interface { getId() string } //Customer struct type Customer struct { id string //sequence generator name string ssn string } // Customer class method getId func (customer Customer) getId() string { //fmt.Println("getting customer Id") return customer.id } //Employee struct type Employee struct { id string name string } //Employee class method getId func (employee Employee) getId() string { return employee.id } //Manager struct type Manager struct { id string name string dept string }
The DataTransferObject
interface is implemented by the Manager
class, as shown in the following code:
//Manager class method getId func (manager Manager) getId() string { return manager.id } //Address struct type Address struct { id string streetLine1 string streetLine2 string state string city string } //Address class method getId func (address Address) getId() string{ return address.id } //main method func main() { var factory = DataTransferObjectFactory{make(map[string]DataTransferObject)} var customer DataTransferObject = factory.getDataTransferObject("customer") fmt.Println("Customer ",customer.getId()) var employee DataTransferObject = factory.getDataTransferObject("employee") fmt.Println("Employee ",employee.getId()) var manager DataTransferObject = factory.getDataTransferObject("manager") fmt.Println("Manager",manager.getId()) var address DataTransferObject = factory.getDataTransferObject("address") fmt.Println("Address",address.getId()) }
Â
Â
Â
Run the following commands:
go run flyweight.go
The following screenshot displays the output:

We will take a look at Private class and Proxy data patterns in the next sections.
The private class data pattern secures the data within a class. This pattern encapsulates the initialization of the class data. The write privileges of properties within the private class are protected, and properties are set during construction. The private class pattern prints the exposure of information by securing it in a class that retains the state. The encapsulation of class data initialization is a scenario where this pattern is applicable.
Account
is a class with account details and a customer name. AccountDetails
is the private attribute of Account
 , and CustomerName
is the public attribute. JSON marshaling of Account
has CustomerName
as a public property. AccountDetails
is the package property in Go (modeled as private class data):
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt and encoding/json packages import ( "encoding/json" "fmt" ) //AccountDetails struct type AccountDetails struct { id string accountType string } //Account struct type Account struct { details *AccountDetails CustomerName string } // Account class method setDetails func (account *Account) setDetails(id string, accountType string) { account.details = &AccountDetails{id, accountType} }
As shown in the following code, the Account
class has the getId
 method, which returns the id
 private class attribute:
//Account class method getId func (account *Account) getId() string{ return account.details.id } //Account class method getAccountType func (account *Account) getAccountType() string{ return account.details.accountType }
The main
method calls the Account
initializer with CustomerName
. The details of the account are set details with the setDetails
method:
// main method func main() { var account *Account = &Account{CustomerName: "John Smith"} account.setDetails("4532","current") jsonAccount, _ := json.Marshal(account) fmt.Println("Private Class hidden",string(jsonAccount)) fmt.Println("Account Id",account.getId()) fmt.Println("Account Type",account.getAccountType()) }
Run the following commands:
go run privateclass.go
The following screenshot displays the output:

Let's take a look at Proxy pattern in the next section.
The proxy pattern forwards to a real object and acts as an interface to others. The proxy pattern controls access to an object and provides additional functionality. The additional functionality can be related to authentication, authorization, and providing rights of access to the resource-sensitive object. The real object need not be modified while providing additional logic. Remote, smart, virtual, and protection proxies are the scenarios where this pattern is applied. It is also used to provide an alternative to extend functionality with inheritance and object composition. A proxy object is also referred to as a surrogate, handle, or wrapper.
The proxy pattern comprises the subject interface, the RealSubject
class, and the Proxy
class:
- Subject is an interface for theÂ
RealObject
andProxy
class. - The
RealSubject
object is created and maintained as a reference in theÂProxy
class.ÂRealSubject
is resource sensitive, required to be protected, and expensive to create. ÂRealObject
is a class that implements theÂIRealObject
interface. It has aperformAction
method. VirtualProxy
is used to accessRealObject
and invoke theÂperformAction
method.
The following code shows an implementation of proxy pattern:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) //IRealObject interface type IRealObject interface { performAction() } //RealObject struct type RealObject struct{} RealObject class implements IRealObject interface. The class has method performAction. //RealObject class method performAction func (realObject *RealObject) performAction() { fmt.Println("RealObject performAction()") } //VirtualProxy struct type VirtualProxy struct { realObject *RealObject } //VirtualProxy class method performAction func (virtualProxy *VirtualProxy) performAction() { if virtualProxy.realObject == nil { virtualProxy.realObject = &RealObject{} } fmt.Println("Virtual Proxy performAction()") virtualProxy.realObject.performAction() } // main method func main() { var object VirtualProxy = VirtualProxy{} object.performAction() }
Run the following commands:
go run virtualproxy.go
The following screenshot displays the output:

Now that we know the classification of data structures and the design patterns used, let's go ahead and take a look at the representation of algorithms.Â
A flow chart and pseudo code are methods of representing algorithms. An algorithm shows the logic of how a problem is solved. A flow chart has different representation symbols such as Entry, Exit, Task, Input/Output, Decision Point, and Inter Block. A structured program consists of a series of these symbols to perform a specific task. Pseudo code has documentation, action, and flow control keywords to visualize an algorithm. The documentation keywords are TASK and REM. SET, PUT, and GET are the action keywords.
Let's take a look at the different representations of algorithms, that is, flow charts and Pseudo code in the next sections.
The flow control keywords areSET, LOOP, (WHILE, UNTIL), REP, and POST. The following flow chart shows a formula or an algorithm to calculate the dividend given a number of shares, the face value, and the dividend percentage. The start and end are the Entry and Exit symbols. The input number of shares, share face value, and dividend percentage use the Input symbol. The compute dividend and output dividend use the Task symbol and Output symbol respectively:

Â
 In the next section, we'll take a look at pseudo code, representation of algorithms.
Pseudo code is a high-level design of a program or algorithm. Sequence and selection are two constructs used in pseudo code. Pseudo code is easier than a flow chart visualizes the algorithm while pseudo code can be easily modified and updated. Errors in design can be caught very early in pseudo code. This saves the cost of fixing defects later.
To give an example, we want to find the max
value in an array of length n. The pseudo code will be written as follows:
maximum(arr) { n <- len(arr) max <- arr[0] for k <- 0,n do{ Ifarr[k] > max { max <- arr[k] } } return max }
Now that we know the different ways to represent the algorithm, let's take a look at how we can monitor its complexity and performance in the next section.
The efficiency of an algorithm is measured through various parameters, such as CPU time, memory, disk, and network. The complexity is how the algorithm scales when the number of input parameters increases. Performance is a measure of time, space, memory, and other parameters. Algorithms are compared by their processing time and resource consumption. Complexity measures the parameters and is represented by the Big O notation.
The complexity of an algorithm is measured by the speed of the algorithm. Typically, the algorithm will perform differently based on processor speed, disk speed, memory, and other hardware parameters. Hence, asymptotical complexity is used to measure the complexity of an algorithm. An algorithm is a set of steps to be processed by different operations to achieve a task. The time taken for an algorithm to complete is based on the number of steps taken.
Let's say an algorithm iterates through an array, m
, of size 10
and update the elements to the sum of index and200
. The computational time will be 10*t, where t is the time taken to add two integers and update them to an array. The next step will be printing them after iterating over an array. The t time parameter will vary with the hardware of the computer used. Asymptotically, the computational time grows as a factor of 10
, as shown in the following code:
//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() { var m [10]int var k int for k = 0; k < 10; k++ { m[k] = k + 200 fmt.Printf("Element[%d] = %d\n", k, m[k] ) } }
Run the following commands:
go run complexity.go
The following screenshot displays the output:

Let's take a look at the different complexity types in the next sections.
The T(n) time function represents the algorithm complexity based on Big O notation. T(n) = O(n) states that an algorithm has a linear time complexity. Using Big O notation, the constant time, linear time, logarithmic time, cubic time, and quadratic time complexity are different complexity types for an algorithm.
Linear time, O(n), is used as a measure of complexity in scenarios such as linear search, traversing, and finding the minimum and maximum number of array elements. ArrayList and queue are data structures that have these methods. An algorithm that has logarithmic time, O(log n), is a binary search in a tree data structure. Bubble sort, selection sort, and insertion sort algorithms have complexity of quadratic time, O(n2). Big Omega Ω and big Theta Πare notations for the lower and upper bounds for a particular algorithm.
The worst case, best case, average case, and amortized run-time complexity is used for analysis of algorithms. Amortized run-time complexity is referred to as 2n. Asymptotically, it will tend to O(1).
Big O notation is also used to determine how much space is consumed by the algorithm. This helps us find the best and worst case scenarios, relative to space and time.
Let's take a look at linear complexity in the next section.
Â
An algorithm is of linear complexity if the processing time or storage space is directly proportional to the number of input elements to be processed. In Big O notation, linear complexity is presented as O(n). String matching algorithms such as the Boyer-Moore and Ukkonen have linear complexity.
Linear complexity, O(n), is demonstrated in an algorithm as follows:
//main package has examples shown // in Go Data Structures and algorithms book package main // importing fmt package import ( "fmt" ) // main method func main() { var m [10]int var k int for k = 0; k < 10; k++ { m[k] = k * 200 fmt.Printf("Element[%d] = %d\n", k, m[k] ) } }
Run the following commands:
go run linear_complexity.go
The following screenshot displays the output:

Â
Let's take a look at quadratic complexity in the next section.
An algorithm is of quadratic complexity if the processing time is proportional to the square of the number of input elements. In the following case, the complexity of the algorithm is 10*10 = 100. The two loops have a maximum of 10
. The quadratic complexity for a multiplication table of n elements is O(n2).
Quadratic complexity, O(n2), is shown in the following example:
//main package has examples shown // in Go Data Structures and algorithms book package main // importing fmt package import ( "fmt" ) // main method func main() { var k,l int for k = 1; k <= 10; k++ { fmt.Println(" Multiplication Table", k) for l=1; l <= 10; l++ { var x int = l *k fmt.Println(x) } } }
Run the following commands:
go run quadratic_complexity.go
The following screenshot displays the output:

Let's take a look at cubic complexity in the next section.
In the case of cubic complexity, the processing time of an algorithm is proportional to the cube of the input elements. The complexity of the following algorithm is 10*10*10 = 1,000. The three loops have a maximum of 10. The cubic complexity for a matrix update is O(n3).
Cubic complexity O(n3) is explained in the following example:
//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() { var k,l,m int var arr[10][10][10] int for k = 0; k < 10; k++ { for l=0; l < 10; l++ { for m=0; m < 10; m++ { arr[k][l][m] = 1 fmt.Println("Element value ",k,l,m," is", arr[k][l][m]) } } } }
Run the following commands:
go run cubic_complexity.go
The following screenshot displays the output:

Let's take a look at logarithmic complexity in the next section.
An algorithm is of logarithmic complexity if the processing time is proportional to the logarithm of the input elements. The logarithm base is typically 2. The following tree is a binary tree with LeftNode
andRightNode
. The insert operation is of O(log n) complexity, where n is the number of nodes.
Logarithmic complexity is presented as follows:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) // Tree struct type Tree struct { LeftNode *Tree Value int RightNode *Tree }
As shown in the following code, the Tree
class has the insert
method, which inserts the element given m
is the integer element:
// Tree insert method for inserting at m position func (tree *Tree) insert( m int) { if tree != nil { if tree.LeftNode == nil { tree.LeftNode = &Tree{nil,m,nil} } else { if tree.RightNode == nil { tree.RightNode = &Tree{nil,m,nil} } else { if tree.LeftNode != nil { tree.LeftNode.insert(m) } else { tree.RightNode.insert(m) } } } } else { tree = &Tree{nil,m,nil} } } //print method for printing a Tree func print(tree *Tree) { if tree != nil { fmt.Println(" Value",tree.Value) fmt.Printf("Tree Node Left") print(tree.LeftNode) fmt.Printf("Tree Node Right") print(tree.RightNode) } else { fmt.Printf("Nil\n") } }
The main
method calls the insert
method on tree
to insert the 1
, 3
, 5
, and 7
 elements, as shown in the following code:
// main method func main() { var tree *Tree = &Tree{nil,1,nil} print(tree) tree.insert(3) print(tree) tree.insert(5) print(tree) tree.LeftNode.insert(7) print(tree) }
Run the following commands:
go run tree.go
The following screenshot displays the output:

Now that we know about the complexities in algorithms and analyzing their performance, let's take a look at brute force algorithms in the next section.
A brute force algorithm solves a problem based on the statement and the problem definition. Brute force algorithms for search and sort are sequential search and selection sort. Exhaustive search is another brute force algorithm where the solution is in a set of candidate solutions with definitive properties. The space in which the search happens is a state and combinatorial space, which consists of permutations, combinations, or subsets.
Brute Force algorithms are known for wide applicability and simplicity in solving complex problems. Searching, string matching, and matrix multiplication are some scenarios where they are used. Single computational tasks can be solved using brute force algorithms. They do not provide efficient algorithms. The algorithms are slow and non-performant. Representation of a brute force algorithm is shown in the following code:
//main package has examples shown //in Hands-On Data Structures and algorithms with Go book package main // importing fmt package 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) }
Â
Â
Â
Â
go run bruteforce.go
The following screenshot displays the output:

After brute force algorithms, let's cover divide and conquer algorithms in the next section.
A divide and conquer algorithm breaks a complex problem into smaller problems and solves these smaller problems. The smaller problem will be further broken down till it is a known problem. The approach is to recursively solve the sub-problems and merge the solutions of the sub-problems.
Recursion, quick sort, binary search, fast Fourier transform, and merge sort are good examples of divide and conquer algorithms. Memory is efficiently used with these algorithms. Performance is sometimes an issue in the case of recursion. On multiprocessor machines, these algorithms can be executed on different processors after breaking them down into sub-problems. A divide and conquer algorithm is shown in the following code:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" )
As shown in the following code, the Fibonacci method takes the k integer parameter and returns the Fibonacci number for k. The method uses recursion to calculate the Fibonacci numbers. The recursion algorithm is applied by dividing the problem into the k-1
integer and the k-2
 integer:
// fibonacci method given k integer func fibonacci(k int) int { if k<=1{ return 1 } return fibonacci(k-1)+fibonacci(k-2) } // main method func main() { var m int = 5 for m=0; m < 8; m++ { var fib = fibonacci(m) fmt.Println(fib) } }
Run the following commands:
go run divide.go
The following screenshot displays the output:

Let's take a look at what backtracking algorithms are in the next section.
A backtracking algorithm solves a problem by constructing the solution incrementally. Multiple options are evaluated, and the algorithm chooses to go to the next component of the solution through recursion. Backtracking can be a chronological type or can traverse the paths, depending on the problem that you are solving.
Backtracking is an algorithm that finds candidate solutions and rejects a candidate on the basis of its feasibility and validity. Backtracking is useful in scenarios such as finding a value in an unordered table. It is faster than a brute force algorithm, which rejects a large number of solutions in an iteration. Constraint satisfaction problems such as parsing, rules engine, knapsack problems, and combinatorial optimization are solved using backtracking.
The following is an example of a backtracking algorithm. The problem is to identify the combinations of elements in an array of 10 elements whose sum is equal to 18
. The findElementsWithSum
 method recursively tries to find the combination. Whenever the sum goes beyond the k
target, it backtracks:
//main package has examples shown // in Hands-On Data Structures and algorithms with Go book package main // importing fmt package import ( "fmt" ) //findElementsWithSum of k from arr of size func findElementsWithSum(arr[10] int,combinations[19] int,size int, k int, addValue int, l int, m int) int { var num int = 0 if addValue > k { return -1 } if addValue == k { num = num +1 var p int =0 for p=0; p < m; p++ { fmt.Printf("%d,",arr[combinations[p]]) } fmt.Println(" ") } var i int for i=l; i< size; i++ { //fmt.Println(" m", m) combinations[m] = l findElementsWithSum(arr,combinations,size,k,addValue+arr[i],l,m+1) l = l+1 } return num } // main method func main() { var arr = [10]int{1,4,7,8,3,9,2,4,1,8} var addedSum int = 18 var combinations [19]int findElementsWithSum(arr,combinations,10,addedSum,0,0,0) //fmt.Println(check)//var check2 bool = findElement(arr,9) //fmt.Println(check2) }
go run backtracking.go
The following screenshot displays the output:

Â
Â
This chapter covered 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 were presented in this chapter. The chapter covered the performance analysis of data structures and structural design patterns.
We looked at the classification of data structures and structural design patterns. You can use algorithms such as brute force, divide and conquer, and backtracking by calculating the complexity and performance analysis. The choice of algorithm and the use of design patterns and data structures are the key takeaways.Â
In the next chapter, we will discuss data structures in Go. The following data structures will be covered:
- Arrays
- Slices
- Two-dimensional slicesÂ
- Maps
- Give an example where you can use a composite pattern.
- For an array of 10 elements with a random set of integers, identify the maximum and minimum. Calculate the complexity of the algorithm.
- To manage the state of an object, which structural pattern is relevant?
- A window is sub-classed to add a scroll bar to make it a scrollable window. Which pattern is applied in this scenario?
- Find the complexity of a binary tree search algorithm.
- Identify the submatrices of 2x2 in a 3x3 matrix. What is the complexity of the algorithm that you have used?
- Explain with a scenario the difference between brute force and backtracking algorithms.
Â
- A rules engine uses backtracking to identify the rules affected by the change. Show an example where backtracking identifies the affected rules.
- Draw a flow chart for the algorithm of the calculation of profit-loss given the cost price, selling price, and quantity.
- Write the pseudo code for an algorithm that compares the strings and identifies the substring within a string.
The following books are recommended if you want to find out more about Gang of Four design patterns, algorithms, and data structures:
- Design Patterns, by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
- Introduction to Algorithms â Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
- Data structures and Algorithms: An Easy Introduction, by Rudolph Russell