Data Structures in Go

January 31, 2021

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.