Outline
In this blog post, I will introduce what the data structure is and how to use it in Golang. You can see the full source code of this blog post on the link below.
About the Map data structure, you can see another blog post.
Data structure
Data structure means how to store and manage the data(value). The data structure includes the array, list, queue, stack, ring, and others.
Big-O
Before checking the data structure in Golang, let’s see the Big-O notation. The Big-O notation is one of the most commonly used notations representing the temporal and spatial efficiency of the algorithm.
The Big-O notation marks the upper limit that takes the longest time and takes up the most space.
The Big-O notation can represent efficiency in the following order.
O(1) < O(N) < O(N*log2N) < O(N2) < O(N3)
List
The List is one of the most basic linear data structures.
The List has the following form.
type Element struct {
Value interface{}
Next *Element
Prve *Element
}
The List has the value stored in the current variable and pointer variables that allow access to the previous and next values.
In Golang, you can use the container/list package to use the List data structure.
import "container/list"
v := list.New()
To check this, create the main.go file and modify it like the below.
package main
import (
"container/list"
"fmt"
)
func main() {
l := list.New()
element4 := l.PushBack(4)
element2 := l.PushFront(1)
l.InsertBefore(3, element4)
l.InsertAfter(2, element2)
fmt.Println("From Front")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println()
fmt.Println("From Back")
for e := l.Back(); e != nil; e = e.Prev() {
fmt.Print(e.Value, " ")
}
}
When the code is executed, you can see the following result.
# go run main.go
From Front
1 2 3 4
From Back
4 3 2 1
The functions used here are as follows.
- Add element to last: PushBack
- Add element to first: PushFront
- Add element immediately before the specified location: InsertBefore
- Add element immediately after the specified location: InsertAfter
Insert data
In the array, when data is inserted at the front, all data is moved one by one, and then the data is added at the front. Therefore, the case of inserting data in the array becomes an O(N) operation.
In the list, when data is inserted at the front, the element is just created and added at the front. So, the case of inserting data in the list becomes an O(1) operation.
Random access
When you access randomly the data in the array, the array can be accessed directly using the index. So, it becomes the O(1) operation. When you access the specified element in the list, the list must search it from the beginning until the element is found. So, it becomes the O(N) operation.
| Action | Array, Slice | List |
|---|---|---|
| Insert | O(N) | O(1) |
| Delete | O(N) | O(1) |
| Access | O(1) | O(N) |
Therefore, if there are many elements insertion or deletion, it’s better performance to use the list. If there are many accessing the specific elements, it’s better to use the array.
Also, ingeneral when the number of elements is small, the array is processed faster than the list because of the locality of the data. 또한, 일반적으로 요소의 수가 적은 경우, 데이터의 지역성때문에 리스트보다 배열이 더 빠르게 처리됩니다.
- locality of the data: if the data are closer to each other, the cache success rate becomes higher, so the performance becomes higher, too.
Queue
Queue is a data structure with FIFO(First In First Out) structure, and it is widely used to implement the event queue.
In Golang, you can implement the queue using the list like the below.
import "container/list"
type Queue struct {
v *list.List
}
func NewQueue() *Queue {
return &Queue{list.New()}
}
func (q *Queue) Push(v interface{}) {
q.v.PushBack(v)
}
func (q *Queue) Pop() interface{} {
front := q.v.Front()
if front == nil {
return nil
}
return q.v.Remove(front)
}
To check this, modify the main.go file like the below.
package main
import (
"container/list"
"fmt"
)
type Queue struct {
v *list.List
}
func NewQueue() *Queue {
return &Queue{list.New()}
}
func (q *Queue) Push(v interface{}) {
q.v.PushBack(v)
}
func (q *Queue) Pop() interface{} {
front := q.v.Front()
if front == nil {
return nil
}
return q.v.Remove(front)
}
func main() {
queue := NewQueue()
for i := 0; i < 5; i++ {
queue.Push(i)
}
v := queue.Pop()
for v != nil {
fmt.Println(v)
v = queue.Pop()
}
}
When you execute the code, you can see the following result.
# go run main.go
0
1
2
3
4
Stack
Stack is a data structure with LIFO(Last In First Out) structure, and it is widely used to implement the function call stack.
In Golang, you can implement the stack using the list like the below.
import "container/list"
type Stack struct {
v *list.List
}
func NewStack() *Stack {
return &Stack{list.New()}
}
func (q *Stack) Push(v interface{}) {
q.v.PushBack(v)
}
func (q *Stack) Pop() interface{} {
back := q.v.Back()
if back == nil {
return nil
}
return q.v.Remove(back)
}
To check this, modify the main.go file like the below.
package main
import (
"container/list"
"fmt"
)
type Stack struct {
v *list.List
}
func NewStack() *Stack {
return &Stack{list.New()}
}
func (q *Stack) Push(v interface{}) {
q.v.PushBack(v)
}
func (q *Stack) Pop() interface{} {
back := q.v.Back()
if back == nil {
return nil
}
return q.v.Remove(back)
}
func main() {
stack := NewStack()
for i := 0; i < 5; i++ {
stack.Push(i)
}
v := stack.Pop()
for v != nil {
fmt.Println(v)
v = stack.Pop()
}
}
When you execute the code, you can see the following result.
# go run main.go
4
3
2
1
0
Ring
Ring is a data structure that the last element points first element list. In the ring, the last element points the first element, so normally, it has a fixed length, and it is often used when the oldest data can be removed.
- Undo feature: When storing certain commands and canceling execution in a document editor.
- Fixed size buffer: When the buffer doesn’t increase depending on the data and the buffer size is fixed.
- Replay feature: like a game replaying, replaying 10 seconds of the finished game.
You can implement the ring using the list like the below.
import "container/ring"
ring := ring.New(5)
n := ring.Len()
for i := 0; i < n; i++ {
ring.Value = i
ring = ring.Next()
}
To check this, modify the main.go file like the below.
package main
import (
"container/ring"
"fmt"
)
func main() {
ring := ring.New(5)
n := ring.Len()
for i := 0; i < n; i++ {
ring.Value = i
ring = ring.Next()
}
fmt.Println("From Front")
for i := 0; i < n; i++ {
fmt.Print(ring.Value, " ")
ring = ring.Next()
}
fmt.Println("")
fmt.Println("From Back")
for i := 0; i < n; i++ {
fmt.Print(ring.Value, " ")
ring = ring.Prev()
}
}
When the code is executed, you can see the following result.
# go run main.go
From Front
0 1 2 3 4
From Back
0 4 3 2 1
Completed
Done! we’ve seen the list, queue, stack, and ring, which are requently used data structures in Golang. Next, try to use these data structures to manage your data mroe efficiently.
Was my blog helpful? Please leave a comment at the bottom. it will be a great help to me!
App promotion
Deku.Deku created the applications with Flutter.If you have interested, please try to download them for free.
