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.
https://play.golang.org/p/3HpTAxoPC6l
// in Go Data Structures and algorithms book
package main
// importing fmt package
import (
"fmt"
)
// main method
func main() {
var rows int
var cols int
rows = 7
cols = 9
// rows := 7
// cols := 9
var twodslices = make([][]int, rows)
var i int
for i = range twodslices {
twodslices[i] = make([]int, cols)
}
fmt.Println(twodslices)
}https://play.golang.org/p/F5MTsF_Z1J1
// in Go Data Structures and algorithms book
package main
// importing fmt package
import (
"fmt"
)
// main method
func main() {
var TwoDArray [8][8]int
TwoDArray[3][6] = 18
TwoDArray[7][4] = 3
fmt.Println(TwoDArray)
}
Linked lists are linear data structures that hold data in individual objects called nodes. These nodes hold both the data and a reference to the next node in the list. Linked lists are often used because of their efficient insertion and deletion. They can be used to implement stacks, queues, and other abstract data types
Credits to the contributors from biocheatsheet.com
package main
import (
"fmt"
)
// n! = n * (n-1) * (n-2)...* 2 * 1
// code limited to return value based
// int type interger range
func factorial(num int) int {
if num == 0 {
return 1
}
f := num
for i:=num; i>=3; i-- {
f = f * (i - 1)
}
return f
}
func main() {
// Dn't used value beyond int type integer range
fmt.Println("Factorial:",factorial(20))
}package main
import "fmt"
// n! = n * (n-1) * (n-2)...* 2 * 1
// code limited to return value based
// int type interger range
// Recursive function
func fact(n int) int {
// terminate the loop with return
if n == 0 {
return 1
}
// return call fact() function is recursively repeteatly
return n * fact(n - 1)
}
func main() {
fmt.Println(fact(5))
}For numbers which are divisible of both 3 and 5, print “FizzBuzz” instead of the number. Divisible by 3 print “Fizz” and divisible by 5 print “Buzz”
package main
import (
"fmt"
)
func fizzBuzz(num int) {
for v := 1; v <= num; v++ {
if v % 15 == 0 {
fmt.Println("v:", v, "FizzBuzz")
} else if v % 5 == 0 {
fmt.Println("v:", v, "Buzz")
} else if v % 3 == 0 {
fmt.Println("v:", v, "Fizz")
} else {
fmt.Println("v:", v)
}
}
}
func main() {
fizzBuzz(20)
}The time complexity of this algorithm is in the order of O(log n).
The binary search algorithm compares the input value to the middle element of the sorted collection.
// Binary Search
package main
// importing sort package
import (
"fmt"
"sort"
)
// main method
func main() {
var elements []int
elements = []int{1, 3, 16, 10, 28, 31, 36, 45, 75}
var element int
element = 36
var i int
i = sort.Search(len(elements), func(i int) bool { return elements[i] >= element })
if i < len(elements) && elements[i] == element {
fmt.Printf("found element %d at index %d in %v\n", element, i, elements)
} else {
fmt.Printf("element %d not found in %v\n", element, elements)
}
}func Search(n int, f func(int) bool) int
Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) == true implies f(i+1) == true.
When shifting right with a logical right shift ( >> ), the least-significant bit is lost and a 0 is inserted on the other end. For positive numbers, a single logical right shift divides a number by 2, throwing out any remainders.
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1) // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}The time complexity of the linear search algorithm is O(n). This means that the running time increases at most linearly with the size of the input.
// Linear Search
package main
import (
"fmt"
)
// Linear Search function
func LinearSearch(elements []int, findElement int) bool {
var element int
for _, element = range elements {
if element == findElement {
return true
}
}
return false
}
func main() {
var elements []int
elements = []int{15, 48, 26, 18, 41, 86, 29, 51, 20}
fmt.Println(LinearSearch(elements, 48))
}The bubble sort algorithm is a sorting algorithm that compares a pair of neighboring elements and swaps them if they are in the wrong order.
package main
import (
"fmt"
)
//bubble Sorter
func bubbleSorter(integers [11]int) {
isSwapped := true
for isSwapped {
isSwapped = false
for i := 1; i < len(integers); i++ {
if integers[i-1] > integers[i] {
// swap routine
temp := integers[i]
integers[i] = integers[i-1]
integers[i-1] = temp
isSwapped = true
}
}
}
fmt.Println(integers)
}
func main() {
// integers := [11]int{31, 13, 12, 4, 18, 16, 7, 2, 3, 0, 10} short form
var integers = [11]int{31, 13, 12, 4, 18, 16, 7, 2, 3, 0, 10}
fmt.Println("Bubble Sorter")
bubbleSorter(integers)
}https://play.golang.org/p/1ob1N-sZKmp
Note: No nested loop used help in reducing the unnecessary looping of all element even a single pair of the unsorted list.
Shortcoming of Go array is address by Go slice. It can be appended to elements after the capacity has reached its size. Slices are dynamic and can double the current capacity in order to add more elements.
var slice = []int{1,3,5,6}
fmt.Println("Capacity", cap(slice))
fmt.Println("Length", len(slice))
slice = append(slice, 8)
fmt.Println(“Capacity”, cap(slice))
fmt.Println(“Length”, len(slice))https://play.golang.org/p/_8fqAbg2cUJ
Slice and Functions ( call by reference)
package main
import "fmt"
//twiceValue method given slice of int type
func twiceValue(slice []int) {
for i, value := range slice {
slice[i] = 2 * value
}
}
func main() {
var slice = []int{1, 3, 5, 6}
// pass by reference when twiceValue function called
twiceValue(slice)
for i := 0; i < len(slice); i++ {
// Original slice value modified by twiceValue function
fmt.Println("new slice value", slice[i])
}
}