# Data Structures in Go

A data structure is a collection of data values and operations that can be applied to the data. Understanding data structures can help us building algorithms. Let me introduce you to four data structures in this short article because they have advanced data structures and algorithms built on them. Linked List, Stack, Queue, and Binary Tree.

Maybe you noticed that I already made some short explanations about those data structures in my previous articles. They are theories. Simple enough to understand. In this article, we are going to construct them from scratch with Go.

It is a linear data structure consisting of a collection of nodes that together represent a sequence. Each node contains; data and a reference to the next node in the sequence.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 `````` ``````package main import ( "fmt" "math" ) type node struct { value byte next *node } func (n *node) size() uint32 { current := n var size uint32 = 0 for current != nil { current = current.next size++ } return size } func (n *node) empty() bool { return n.size() == 0 } func (n *node) print() { current := n for current != nil { fmt.Print(current.value, " ") current = current.next } fmt.Println() } func (n *node) push(value byte) { if n.size() < math.MaxInt32 { current := n for current.next != nil { current = current.next } current.next = &node{value, nil} } } func (n *node) pop() { if !n.empty() { var previous, current *node = nil, n for current.next != nil { previous = current current = current.next } previous.next = nil } } func (n *node) back() byte { current := n for current.next != nil { current = current.next } return current.value } func (n *node) front() byte { return n.value } func (n *node) at(index uint32) byte { current := n var i uint32 var result byte for current.next != nil && i < index { current = current.next i++ } result = current.value if index > n.size() { result = 0 } return result } func (n *node) insert(value byte, index uint32) { if n.size() < math.MaxInt32 { switch { case index <= 0, index > n.size(): n.push(value) default: current := n var i uint32 for current.next != nil && i < index-1 { current = current.next } tmp := &node{current.value, nil} next := current.next for next != nil { tmp.next = &node{next.value, nil} next = next.next } current.value = value current.next = tmp } } } func (n *node) erase(index uint32) { if !n.empty() && index <= n.size() { switch { case index >= n.size(): var previous, current *node = nil, n for current.next != nil { previous = current current = current.next } previous.next = nil default: var previous, current *node = nil, n var i uint32 for current.next != nil && i < index { previous = current current = current.next i++ } previous.next = current.next } } } func main() { list := node{1, nil} list.push(2) list.push(3) list.pop() list.insert(4, 2) list.erase(2) list.print() fmt.Println(list.back()) fmt.Println(list.front()) fmt.Println(list.size()) fmt.Println(list.empty()) fmt.Println(list.at(2)) } ``````

I created a linked list that has some functions similar to C++ Vector. Understanding linked lists and how they work is essential for understanding subsequent data structures such as binary trees. Next, I also created Stack and Queue on nodes that are similar to linked lists. Remember, a node contains data and reference(s).

Most of the functions or methods above have linear time complexity, or O(n). We can have constant time complexity to get the size and back if we make a constructor for initializing a linked list. But in Go, a constructor is unnecessary because we can initialize directly from the struct. The space complexity for all operations is constant, or O(1).

## Stack

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 `````` ``````package main import ( "fmt" "math" ) type node struct { value byte next *node } func (n *node) print() { current := n for current != nil { fmt.Print(current.value, " ") current = current.next } fmt.Println() } func (n *node) size() uint32 { current := n var size uint32 = 0 for current != nil { current = current.next size++ } return size } func (n *node) empty() bool { return n.size() == 0 } func (n *node) push(value byte) { if n.size() < math.MaxInt32 { current := n for current.next != nil { current = current.next } current.next = &node{value, nil} } } func (n *node) pop() { if !n.empty() { var previous, current *node = nil, n for current.next != nil { previous = current current = current.next } previous.next = nil } } func (n *node) top() byte { current := n for current.next != nil { current = current.next } return current.value } func main() { stack := node{1, nil} stack.push(2) stack.push(3) stack.pop() stack.print() fmt.Println(stack.top()) fmt.Println(stack.size()) fmt.Println(stack.empty()) }``````

## Queue

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 `````` ``````package main import ( "fmt" "math" ) type node struct { value byte next *node } func (n *node) size() uint32 { current := n var size uint32 = 0 for current != nil { current = current.next size++ } return size } func (n *node) empty() bool { return n.size() == 0 } func (n *node) print() { current := n for current != nil { fmt.Print(current.value, " ") current = current.next } fmt.Println() } func (n *node) push(value byte) { if n.size() < math.MaxInt32 { current := n for current.next != nil { current = current.next } current.next = &node{value, nil} } } func (n *node) pop() { if !n.empty() { var previous, current *node = nil, n for current.next != nil { previous = current current.value = current.next.value current = current.next } previous.next = nil } } func (n *node) back() byte { return n.value } func (n *node) front() byte { current := n for current.next != nil { current = current.next } return current.value } func main() { queue := node{1, nil} queue.push(2) queue.push(3) queue.pop() queue.print() fmt.Println(queue.back()) fmt.Println(queue.front()) fmt.Println(queue.size()) fmt.Println(queue.empty()) }``````

Refer to my previous article about Stack vs Queue for the theory.

You can see that our code is simpler than the linked list. My references are C++ Stack and C++ Queue.

## Binary Tree

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 `````` ``````package main import "fmt" type node struct { value byte left *node right *node } func (n *node) print() { fmt.Println(n.value) if n.left != nil { n.left.print() } if n.right != nil { n.right.print() } } func (n *node) push(value byte) { switch { case value < n.value: if n.left == nil { n.left = &node{value, nil, nil} } else { n.left.push(value) } default: if n.right == nil { n.right = &node{value, nil, nil} } else { n.right.push(value) } } } func main() { tree := &node{5, nil, nil} tree.push(3) tree.push(7) tree.push(1) tree.push(2) tree.push(6) tree.push(8) tree.print() }``````

Refer to my previous article about Binary Tree for the theory.

We created a simple binary tree with recursive functions. In our binary tree above, the low value will be added to the left, and the high one will be added to the right.

## Closing

Actually, Go is a simple language. It provides some packages to build linked lists or trees. You can get them on https://golang.org/pkg/container/.

You can find the source code at https://github.com/aristorinjuang/go-data-structures. Maybe you noticed there are several operations to improve in time complexity from linear O(n) to constant O(1). I mentioned it before. Maybe you want to add a function to visualize the tree in stdout or even invert it. Feel free to optimize.