# 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.

## Linked List

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.