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. Thesquareand 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 powerSeriesfunction, 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

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:

Let's say you have an IProcessor interface with a processmethod, 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 IContourbridge 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{}

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

drawContour method

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:

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 processmethod 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:

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

Run the following commands:

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:

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:

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. 

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(n²). 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 2ⁿ. 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(n²).

Quadratic complexity, O(n²), 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(n³).

Cubic complexity O(n³) 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 LeftNodeandRightNode. 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.