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

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

## Queue

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

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.