1 Golang common data structure implementation
1.1 Link List
Take the example of single linked lists, the same is true for two-way linked lists, just like it has more pre pointers.
Define a single linked list structure:
type LinkNode struct {
Data int64
NextNode *LinkNode
}
Constructing and printing list:
func main() {
node := new(LinkNode)
= 1
node1 := new(LinkNode)
= 2
= node1 // node1 is linked to node node
node2 := new(LinkNode)
= 3
= node2 // node2 is linked to node1 node
// Print in sequence. Assign the original link header node to the new NowNode // This still keeps the node node of the original link header nowNode := node
for nowNode != nil {
()
// Get the next node. Linked list slides down nowNode =
}
}
1.2 Variable arrays
Variable arrays are very commonly used in various languages. In golang, the variable array language itself has been implemented, which is our slice slice.
1.3 Stack and Queue
1.3.1 Native slice implementation stack and queue
Stack: first in and then out, later in and first out, similar to magazine
Queue: First-in, First-out
In golang, it is very simple to implement concurrent unsafe stacks and queues. We can just use native slices directly.
1.3.1.1 Slice native stack implementation
func main() {
// Make a stack with slices var stack []int
// Element 1 enters the stack stack = append(stack, 1, 5, 7, 2)
// The stack takes out the most recently added data. For example [1,5,7,2], len = 4 x := stack[len(stack)-1] // 2
// Cut out the recently added data, imitate the pop of the stack in the previous step and this step. stack = stack[:len(stack)-1] // [1,5,7]
("%d", x)
}
1.3.1.2 Slice native queue implementation
func main() {
// Imitate the queue with slices var queue []int
// Enter the queue queue = append(queue, 1, 5, 7, 2)
// The team head pops up, then cuts off the team head to imitate the poll operation of the queue cur := queue[0]
queue = queue[1:]
("%d", cur)
}
1.3.2 *Concurrent and safe stacks and queues
1.3.2.1 Slicing to achieve concurrent and secure stack
// Array stack, later in and first outtype Mystack struct {
array []string // The bottom slice size int // Number of elements on the stack lock // Lock for concurrent and safe use}
Enter the stack
// Enter the stackfunc (stack *Mytack) Push(v string) {
()
defer ()
// Put it into a slice, and the backward elements are placed at the end of the array = append(, v)
// Number of elements in the stack +1 = + 1
}
Out the stack
1. If the slice offset moves forward [0: -1], it means that the last element no longer belongs to the array, and the array is reduced in disguise. At this time, the part of the slice being reduced is not recycled and still occupies space, so the space complexity is high, but the operation time complexity is: O(1).
2. If we create a new array newArray and then copy the elements of the old array to the new array, it will not take up extra space, but the number of movements is too many, and the time complexity is: O(n).
func (stack *Mystack) Pop() string {
()
defer ()
// Elements in the stack are empty if == 0 {
panic("empty")
}
// Top element of stack v := [-1]
// Slices shrink, but may take up more and more space // = [0 : -1]
// Create a new array, the space usage will not increase, but the number of elements may be moved too much newArray := make([]string, -1, -1)
for i := 0; i < -1; i++ {
newArray[i] = [i]
}
= newArray
// Number of elements in the stack -1 = - 1
return v
}
Get the top element of the stack
// Get the top element of the stackfunc (stack *Mystack) Peek() string {
// Elements in the stack are empty if == 0 {
panic("empty")
}
// Top element value of stack v := [-1]
return v
}
Get the stack size and determine whether it is empty
// Stack sizefunc (stack *Mystack) Size() int {
return
}
// Is the stack emptyfunc (stack *Mystack) IsEmpty() bool {
return == 0
}
1.3.2.2 Slicing implements concurrent and safe queue structure
// Array queue, first in first outtype Myqueue struct {
array []string // The bottom slice size int // Number of elements in the queue lock // Lock for concurrent and safe use}
Join the team
// Join the teamfunc (queue *Myqueue) Add(v string) {
()
defer ()
// Put it into a slice, and the backward elements are placed at the end of the array = append(, v)
// Number of elements in the team +1 = + 1
}
Departure
1. Move the position in place, fill in [i-1] = [i] in turn, and then reduce the array size: = [0: -1], but in this way, the memory space that is sliced and reduced will not be released.
2. Create a new array and move elements other than the first element in the old array to the new array.
// Departurefunc (queue *Myqueue) Remove() string {
()
defer ()
// The elements in the team are empty if == 0 {
panic("empty")
}
// The front element of the queue v := [0]
/* Move directly in situ, but the subsequent space of shrinking will not be released
for i := 1; i < ; i++ {
// Start data movement from the first position
[i-1] = [i]
}
// Original array size reduction
= [0: -1]
*/
// Create a new array with too many moves newArray := make([]string, -1, -1)
for i := 1; i < ; i++ {
// Start data movement from the first bit of the old array newArray[i-1] = [i]
}
= newArray
// Number of elements in the team-1 = - 1
return v
}
1.4 Dictionary Map and Collection Set
1.4.1 Map
Dictionaries are also structures commonly used by programming languages. Dictionaries in golang are map structures that they implement themselves. For specific operations, you can view the language api
A concurrently secure map can define a structure, with a map member and a lock variable member in the structure, referring to the implementation of concurrently secure stack and queue. Go language also implements a concurrent and secure map, the specific reference API
1.4.2 Set
We can use the features of map to implement a Set structure.
Set structure
We do not apply the value of map, the struct{} defined as empty
// Collection structuretype Set struct {
m map[int]struct{} // Use a dictionary to implement it, because the field keys cannot be repeated len int // The size of the collection // Lock to achieve concurrent security}
Initialize Set
// Create a new empty collectionfunc NewSet(cap int64) *Set {
temp := make(map[int]struct{}, cap)
return &Set{
m: temp,
}
}
Add an element to set
// Add an elementfunc (s *Set) Add(item int) {
()
defer ()
[item] = struct{}{} // Actually add this key to the dictionary = len() // Recalculate the number of elements}
Delete an element
// Remove an elementfunc (s *Set) Remove(item int) {
()
()
// Return the collection directly without elements if == 0 {
return
}
delete(, item) // Actually delete this key from the dictionary = len() // Recalculate the number of elements}
Check whether the element is in the collection set
// Check if the element existsfunc (s *Set) Has(item int) bool {
()
defer ()
_, ok := [item]
return ok
}
View collection size
// Check the collection sizefunc (s *Set) Len() int {
return
}
Check whether the collection is empty
// The set is empty enoughfunc (s *Set) IsEmpty() bool {
if () == 0 {
return true
}
return false
}
Clear all elements of the collection
// Clear all elements of the collectionfunc (s *Set) Clear() {
()
defer ()
= map[int]struct{}{} // Dictionary reassignment = 0 // Size to zero}
Convert collections into slices
func (s *Set) List() []int {
()
defer ()
list := make([]int, 0, )
for item := range {
list = append(list, item)
}
return list
}
1.5 Binary Tree
Binary tree: A tree with only two son nodes per node at most.
Full binary tree: A binary tree with a height difference of 0 between the leaf node and the leaf node, that is, the whole tree is full and the tree is full of triangle structure. In foreign definition, non-leaf node sons are full of trees, which are full of binary trees. We shall prevail in China.
Complete binary tree: A complete binary tree is derived from a full binary tree. Assuming the depth of the binary tree is k, except for the kth layer, the number of nodes in other layers reaches the maximum value, and all nodes in the kth layer are continuously concentrated on the leftmost.
Binary tree structure definition
// Binary Treetype TreeNode struct {
Data string // Nodes are used to store data Left *TreeNode // Left Scholar Tree Right *TreeNode // Right tree}
Traversal of the tree
1. First order traversal: first access the root node, then access the left subtree, and finally access the right subtree.
2. Post-order traversal: first access the left subtree, then the right subtree, and finally access the root node.
3. In-order traversal: first access the left subtree, then access the root node, and finally access the right subtree.
4. Hierarchical traversal: Each layer accesses each node from left to right.
// traversal in advancefunc PreOrder(tree *TreeNode) {
if tree == nil {
return
}
// Print the root node first (, " ")
// Print the left subtree PreOrder()
// Print the right character tree again PreOrder()
}
// In-order traversalfunc MidOrder(tree *TreeNode) {
if tree == nil {
return
}
// Print the left subtree first MidOrder()
// Print the root node again (, " ")
// Print the right character tree again MidOrder()
}
// Post-order traversalfunc PostOrder(tree *TreeNode) {
if tree == nil {
return
}
// Print the left subtree first MidOrder()
// Print the right character tree again MidOrder()
// Print the root node again (, " ")
}
Traversal by layer:
func Level(head *TreeNode) {
if head == nil {
return
}
// Imitate the queue with slices var queue []*TreeNode
queue = append(queue, head)
for len(queue) != 0 {
// The team head pops up, then cuts off the team head to imitate the poll operation of the queue cur := queue[0]
queue = queue[1:]
("%d", (*cur).Data)
// There is a left child at the current node, join the left child to enter the queue if != nil {
queue = append(queue, )
}
// There is a right child at the current node, join the right child and enter the queue if != nil {
queue = append(queue, )
}
}
}
This is the end of this article about implementing common data structures using go. For more related content on implementing data structures, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!