1.Go-copy function, sort sorting, doubly linked list, list operation and doubly circular linked list

1.Go-copy function, sort sorting, doubly linked list, list operation and doubly circular linked list

1.1.copy function

The content of one slice can be copied to another slice through the copy function

(1) Copy the long slice to the short slice

package main

import "fmt"

func main() {
	s1 := []int {1,2}
	s2 := []int{3,4,5,6}
	//copy is a corner mark and will not increase the length of the meta slice
	copy(s1,s2)
	fmt.Println(s1)//[3 4]
	fmt.Println(s2)//[3 4 5 6]
}

(2) Copy the short slice to the long slice 

package main

import "fmt"

func main() {
	s1 := []int {1,2}
	s2 := []int{3,4,5,6}
	//copy is a corner mark and will not increase the length of the meta slice
	copy(s2,s1)
	fmt.Println(s1)//[1 2]
	fmt.Println(s2)//[1 2 5 6]
}

(3) Copy the slice segment to the slice

package main

import "fmt"

func main() {
	s1 := []int {1,2}
	s2 := []int{3,4,5,6}
	//copy is a corner mark and will not increase the length of the meta slice
	copy(s1,s2[1:3])
	fmt.Println(s1)//[[4 5]
	fmt.Println(s2)//[3 4 5 6]
}

1.2.sort sort

package main

import (
	"fmt"
	"sort"
)

func main() {
	num := []int{1,7,3,5,2}
	//Sort in ascending order
	sort.Ints(num)
	fmt.Println(num)//[1 2 3 5 7]

	//Sort in descending order
	sort.Sort(sort.Reverse(sort.IntSlice(num)))
	fmt.Println(num)//[7 5 3 2 1]
}

1.3. Doubly linked list

 (1) The structure of a doubly linked list

The elements in the doubly linked list structure are not in the immediate vicinity of the memory space, but the addresses of the previous element and the next element are stored in each element

  • The first element is called the (head) element, and the front connection (front pointer field) is nil
  • The last element is called the foot element, after the connection (post pointer field) the end is nil

 Advantages of doubly linked list

  • It is efficient when executing adding or deleting elements. To get any element, you can easily insert elements before and after this element
  • Make full use of memory space and realize flexible memory management
  • Realize positive and reverse order traversal
  • High efficiency when adding or deleting head and tail elements

  Disadvantages of doubly linked lists

  •  The linked list adds the pointer field of the element, and the space overhead is relatively large
  • Search content jumps during traversal, low traversal performance for large amounts of data

 (2) Doubly linked list container List

The container/list package of the Go language standard library provides a doubly linked list List

The List structure is defined as follows

  • root represents the root element
  • len indicates how many elements are in the linked 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
}

 The Element structure is defined as follows

  • next represents the next element, which can be obtained by using Next()
  • prev represents the previous element, which can be obtained by using Prev()
  • list indicates which linked list the element belongs to
  • Value represents the value of the element, 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{}
}

1.4. Operation List

(1) Directly use New() under the container/list package to create an empty List

Add, traverse, take the beginning and end, take the middle element

package main

import (
	"container/list"
	"fmt"
)

func main() {
	//Instantiate
	mylist := list.New()
	fmt.Println(mylist)

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

	//Traversal
	for e := mylist.Front(); e != nil; e = e.Next(){
		fmt.Print(e.Value, "")//aebdc
	}
	fmt.Println("")

	//Take the beginning and end
	fmt.Println(mylist.Front().Value)//a
	fmt.Println(mylist.Back().Value)//c

	//Take the element in the middle and pass the continuous Next()
	n := 3
	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("The value of n is wrong")
	}
	fmt.Println(curr.Value)//b
}

(2) Moving elements 

package main

import (
	"container/list"
	"fmt"
)

func main() {
	//Instantiate
	mylist := list.New()
	fmt.Println(mylist)

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

	//Move, put the first element in front of the last element
	mylist.MoveBefore(mylist.Front(),mylist.Back())
	//mylist.MoveAfter(mylist.Back(),mylist.Front())
	
	//Move the last element to the front
	//mylist.MoveToFront(mylist.Back())
	//Move the first element to the back
	//mylist.MoveToBack(mylist.Front())

	for e := mylist.Front(); e != nil; e = e.Next(){
		fmt.Print(e.Value, "")//ebdac
	}
}

(3) Delete

mylist.Remove(mylist.Front())

1.5. Two-way circular list

(1) The characteristic of circular linked list is that the pointer field without nodes is nil, and other elements can be found through any element

The structure of the circular linked list is as follows

The difference between a doubly circular linked list and a doubly linked list

  • Two-way circular linked list does not have the head element and the tail element in the strict sense
  • The front and back connections without elements are nil
  • A two-way circular linked list of length n, moving in a certain direction through a certain element, after searching up to n-1 times, another element will be found

(2) The structure Ring source code under the container/ring package is as follows

  • The official clearly stated that Ring is an element of a circular linked list, and it is also a circular linked list.
  • In actual use, Ring traversal is the first element of the circular linked 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
}

(3) Create and view  

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	//r represents the entire circular linked list, and represents the first element
	r := ring.New(5)
	r.Value = 0
	r.Next().Value = 1
	r.Next().Next().Value = 2
	//r.Next().Next().Next().Value = 3
	//r.Next().Next().Next().Next().Value = 4
	r.Prev().Value = 4
	r.Prev().Prev().Value = 3
	//View element content
	//There are several elements in the circular linked list, func will be executed several times, and the content of the element currently executed
	r.Do(func(i interface{}) {
		fmt.Print(i, "")//0 1 2 3 4
	})
	fmt.Println("")
	//Take the middle element and use move
	fmt.Println(r.Move(3).Value)//3


}

(4) Increase

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	//r represents the entire circular linked list, and represents the first element
	r := ring.New(5)
	r.Value = 0
	r.Next().Value = 1
	r.Next().Next().Value = 2
	//r.Next().Next().Next().Value = 3
	//r.Next().Next().Next().Next().Value = 4
	r.Prev().Value = 4
	r.Prev().Prev().Value = 3

	//increase
	r1 := ring.New(2)
	r1.Value = 5
	r1.Next().Value = 6
	r.Link(r1)

	r.Do(func(i interface{}) {
		fmt.Print(i, "")//0 5 6 1 2 3 4 
	})
}

(5) Delete

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	//r represents the entire circular linked list, and represents the first element
	r := ring.New(5)
	r.Value = 0
	r.Next().Value = 1
	r.Next().Next().Value = 2
	//r.Next().Next().Next().Value = 3
	//r.Next().Next().Next().Next().Value = 4
	r.Prev().Value = 4
	r.Prev().Prev().Value = 3

	//delete
	r.Unlink(1)

	r.Do(func(i interface{}) {
		fmt.Print(i, "")//0 2 3 4 
	})
}

Delete the last two

//delete
	r.Unlink(2)

	r.Do(func(i interface{}) {
		fmt.Print(i, "")//0 3 4 
	})

r.Next() delete

//delete
	r.Next().Unlink(2)

	r.Do(func(i interface{}) {
		fmt.Print(i, "")//0 1 4 
	})qu  

Out of range, take the remainder of 5

//delete
	r.Unlink(6)

	r.Do(func(i interface{}) {
		fmt.Print(i, "")//0 2 3 4
	})
Reference: https://cloud.tencent.com/developer/article/1481006 1. Go-copy function, sort sort, doubly linked list, list operation and doubly circular linked list-Cloud + Community-Tencent Cloud