“This is the 16th day of my participation in the August Gwen Challenge

Sort the package

• Sort provides the sorting API in the Go language standard library
• The Sort package provides a variety of sorting algorithms that are implemented internally, and the optimal algorithm implementation is automatically selected each time a sort package is used
  • Insertion sort
  • Quick sort
  • Heap row
• The top layer of the sort package is an Interface named Interface, which can be sorted as long as it satisfies the sort.Interface type

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)}Copy the code

• By default, the Go library provides an API for sorting int, float64, and String
• Many functions have arguments of type in the SORT package and need to be converted.

Sorting implementation

• Sort int slices

	num := [] int{1.7.5.2.6}
	sort.Ints(num) / / ascending
	fmt.Println(num)
	sort.Sort(sort.Reverse(sort.IntSlice(num))) / / descending
	fmt.Println(num)
Copy the code

• Sort slices of type float64

	f := [] float64{1.5.7.2.5.8.2.3.6.9}
	sort.Float64s(f) / / ascending
	fmt.Println(f)
	sort.Sort(sort.Reverse(sort.Float64Slice(f))) / / descending
	fmt.Println(f)
Copy the code

• Sort string slices
  • Sort by code table value
  • Multiple strings are compared by the first character
  • If the first character is the same, compare the second character

	s := []string{"我"."I am Goer"."a"."d"."Country"."You"."I'm a"}
	sort.Sort(sort.StringSlice(s)) / / ascending
	fmt.Println(s)
	// Find the index of the content, if it does not exist, return where the content should be inserted in the ascending sort slice
	fmt.Println(sort.SearchStrings(s, "Are you"))
	sort.Sort(sort.Reverse(sort.StringSlice(s)))
	fmt.Println(s)
Copy the code

map

• Map stores a collection of key-value pairs in a hash table

• Each element in the map is a key-value pair

map[key]Value
Copy the code

• Key is the only criterion for manipulating a map. You can add, delete, modify, and view elements in the map using keys
• Keys are unique, and adding duplicate keys overwrites previous elements.
• Map is a value type, null pointer when declared only (nil)

	var m map[string]int
	fmt.Println(m == nil) / / output: true
	fmt.Printf("%p", m)   / / output: 0 x0
Copy the code

• Map reading and writing data is not concurrently safe, but can be combined with RWMutex to ensure concurrency security.

Several ways to instantiate a map

• Use the make function to instantiate a map with no initial values

	m := make(map[string]string)
	fmt.Println(m==nil)/ / output: false
	fmt.Printf("%p", m)// Output: memory address
Copy the code

• You can assign an initial value to a map directly when you declare it. Note the syntax difference between initial values on one line and multiple lines
  • The key-value pairs of elements in the map can be: key:value
  • The key and value types must correspond to the map[key]value types

	m := map[string]string{"name": "msr"."address": Guangdong, China}
	m1 := map[string]string{
		"name":     "msr"."addresss": Guangdong, China,
	}
	fmt.Println(m, m1)
Copy the code

Manipulate elements in the map

• If the key does not exist, data is added to the map. If the key does exist, elements in the map are overwritten

	m := make(map[string]int)
	m["money"] = 5
	fmt.Println(m) / / output: the map [5] money:
	m["money"] = 6
	fmt.Println(m) //map[money:6]
Copy the code

• The Go language standard library provides a function to delete map elements, which can be completed by using the top-level delete()
  • Delete the element if the key exists
  • If the key does not exist, the map does not contain any errors

	m := make(map[string]int)
	m["money"] = 5
	delete(m, "No key.")
	fmt.Println(m) / / output: the map [5] money:
	delete(m, "money")
	fmt.Println(m) / / output: the map []
Copy the code

• Gets the value of the specified key in the map
  • Use the :map variable [key] to obtain the value of the key
  • Return the default Value of the Value type in map[key]Value if the key does not exist. For example, if Value is string, return “”.
  • The return value can be one or two.
    • A value representing the corresponding key
    • Value of key and whether the key exists

	m := map[string]string{"name": "msr"."address": Guangdong, China}
	fmt.Println(m["name"]) / / output: MSR
	fmt.Println(m["age"])  // Output: empty string
	value, ok := m["age"]
	fmt.Println(value, ok) // Output: empty string false
Copy the code

• If you want to iterate through all the elements of the map, you can use for with range

	m := map[string]string{"name": "msr"."address": Guangdong, China}
	//range Returns key and value when traversing the map
	for key, value := range m {
		fmt.Println(key, value)
	}
Copy the code

Overview of bidirectional linked lists

• The structure of the bidirectional list is as follows

• In a bidirectionally linked list structure, elements are not located next to each other in memory, but each element contains the address of the previous and the next element

  • The first element is called the head element, and the front join (the front pointer field) is nil
  • The last element is called the foot element, and the post-join (post-pointer field) is nil

• Advantages of bidirectional linked lists:

  • In the implementation of new elements or delete elements of high efficiency, to obtain any element, you can easily insert before and after the element
  • Make full use of memory space to achieve flexible memory management
  • Positive order and reverse order traversal can be realized
  • Header and tail elements can be added or deleted efficiently

• Disadvantages of bidirectional linked lists

  • Linked lists increase the pointer field of elements, which is expensive in space
  • Traversal jumps to find content, and the traversal performance of large amounts of data is low

Bidirectional linked List container List

• The Container/List package in the Go language standard library provides a bidirectional list list
• The List structure is defined as follows
  • Root indicates the root element
  • Len is how many elements there are in the list

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}
Copy the code

• The Element structure is defined as follows
  • Next represents the next element, which can be retrieved using next ()
  • Prev represents the previous element, which can be retrieved using prev ()
  • List indicates which linked list the element belongs to
  • Value represents the Value of an element, and interface{} represents any type in the Go language

  // Element is an element of a linked list.
  type Element struct {
  	// Next and previous pointers in the doubly-linked list of elements.
  	// To simplify the implementation, internally a list l is implemented
  	// as a ring, such that &l.root is both the next element of the last
  	// list element (l.Back()) and the previous element of the first list
  	// element (l.Front()).
  	next, prev *Element

  	// The list to which this element belongs.
  	list *List

  	// The value stored with this element.
  	Value interface{}}Copy the code

Operating the List

• Create an empty list directly using New() in the container/list package

	mylist := list.New()
	fmt.Println(mylist)       // Print the contents of the list
	fmt.Println(mylist.Len()) // Check the number of elements in the list
	fmt.Printf("%p", mylist)  // Output address
Copy the code

• The Go language standard library provides many functions for adding elements to bidirectional lists

	// add to end,List["a"]
	mylist.PushBack("a")
    List["b","a"]
	mylist.PushFront("b") 
	List["b","c","a"]
	mylist.InsertAfter("c", mylist.Front()) 
	// Add the element before the last element,List["b","c","d","a"]
	mylist.InsertBefore("d", mylist.Back()) 
Copy the code

• Retrieves the elements in the linked list

	fmt.Println(mylist.Back().Value)  // The value of the last element
	fmt.Println(mylist.Front().Value) // The value of the first element

	// You can only look backwards or backwards to get the element content
	n := 5
	var curr *list.Element
	if n > 0 && n <= mylist.Len() {
		if n == 1 {
			curr = mylist.Front()
		} else if n == mylist.Len() {
			curr = mylist.Back()
		} else {
			curr = mylist.Front()
			for i := 1; i < n; i++ {
				curr = curr.Next()
			}
		}
	} else {
		fmt.Println("N is not the right number.")}// Iterate over all values
	fore := mylist.Front(); e ! =nil; e = e.Next() {
		fmt.Println(e.Value)
	}
Copy the code

• Move the order of elements

	mylist.MoveToBack(mylist.Front()) // Move the first one behind
	mylist.MoveToFront(mylist.Back()) // Move the last one forward
	mylist.MoveAfter(mylist.Front(),mylist.Back())// Move the first parameter element after the second
	mylist.MoveBefore(mylist.Front(),mylist.Back())// Move the first parameter element to the front of the second
Copy the code

• Remove elements

mylist.Remove(mylist.Front())
Copy the code

Bidirectional circular linked lists

• A circular list is characterized by a pointer field with no nodes that is nil, through which any element can be found other elements
• The structure of the circular list is as follows

graph LR
	A -->B	
	B -->C	
	C -->D	
	D -->E
	E -->D
	A -->E
	E -->A
	D -->C
	C -->B
	B -->A	

• Bidirectional cyclic lists are different from bidirectional lists

  • A bidirectional circular list has no strict head and tail elements
  • Pre-join and post-join without elements are nil
  • A bidirectional circular list of length N, moving through one element in one direction, must find another element after at most n-1 searches

Bidirectional cyclic linked lists in Go

• In the container/ring package, the source code for the ring structure is as follows
  • Officially, it is clearly stated that Ring is an element of a circular list, which is also a circular list.
  • In practice, Ring traversal is the first element of a circular list

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
	next, prev *Ring
	Value      interface{} // for use by client; untouched by this library
}
Copy the code

• The Go standard library provides the following apis for container/ Ring packages

	type Ring
		// Instantiate a circular list of length n
		func New(n int) *Ring
		/ / the length
		func (r *Ring) Len(a) int
		// Next element
		func (r *Ring) Next(a) *Ring
		// The previous element
		func (r *Ring) Prev(a) *Ring
		// Move n times, supporting negative numbers
		func (r *Ring) Move(n int) *Ring
		// merge s and r
		func (r *Ring) Link(s *Ring) *Ring
		// delete the n% r.len () element after r
		func (r *Ring) Unlink(n int) *Ring
		// Loop through, I is the current element value
		func (r *Ring) Do(f func(interface{}))
Copy the code

Code demo

• Instantiate, assign, traverse

	r := ring.New(3)
	for i := 0; i < r.Len(); i++ {
		r.Move(i).Value = i
	}
	r.Do(func(i interface{}) {
		fmt.Println(i)
	})
Copy the code

• The instantiated r is the first element created in the linked list. You can find the elements before and after the element

	fmt.Println(r.Next().Value)/ / output: 1
	fmt.Println(r.Next().Next().Value)/ / output: 2
	fmt.Println(r.Next().Next().Next().Value)/ / output: 0
	fmt.Println(r.Move(- 1).Value)/ / output: 2
	fmt.Println(r.Prev().Value)/ / output: 2
Copy the code

• You can add or remove lists to circular lists

	s := ring.New(1)
	s.Value = 13
	// add the new list to whatever element r is
	r.Link(s)
	r.Do(func(i interface{}) {
		fmt.Print(i, "")
	})
	fmt.Println("")
	// Back from the r element,n/ r.len () elements are removed, the current element and previous ones remain
	r.Unlink(1)
	r.Do(func(i interface{}) {
		fmt.Print(i, "")})Copy the code

Golang learning a: start from the environment configuration to HelloWorld entry GOLang learning two: Golang own tools olang learning three: Golang basic grammar Golang learning four: flow control golang learning five: common mathematical functions and arrays Golang learning six: Golang for loops golang for loops golang for loops Golang for loops golang for loops golang for loops golang for loops Package access, variable scope, closure Golang learning twelve: Value passing and reference passing Golang learning thirteen: structure Golang learning fourteen: Object-oriented Golang learning fifteen: error exception handling Golang learning sixteen: File operation Golang learning seventeen: Reflection Golang learning eighteen: XML operation Golang learning nineteen: log Golang learning twenty: Golang concurrent programming entry Golang learning twenty-one: SELECT and GC