1.1.copy 函数
通过 copy 函数可以把一个切片内容复制到另一个切片中
(1)把长切片拷贝到短切片中
- package main
- import "fmt"
- func main() {
- s1 := []int {1,2}
- s2 := []int{3,4,5,6}
- //copy 的是角标, 不会增加元切片的长度
- copy(s1,s2)
- fmt.Println(s1) //[3 4]
- fmt.Println(s2) //[3 4 5 6]
- }
(2)把短切片拷贝到长切片中
- package main
- import "fmt"
- func main() {
- s1 := []int {1,2}
- s2 := []int{3,4,5,6}
- //copy 的是角标, 不会增加元切片的长度
- copy(s2,s1)
- fmt.Println(s1) //[1 2]
- fmt.Println(s2) //[1 2 5 6]
- }
(3)把切片片段拷贝到切片中
- package main
- import "fmt"
- func main() {
- s1 := []int {1,2}
- s2 := []int{3,4,5,6}
- //copy 的是角标, 不会增加元切片的长度
- copy(s1,s2[1:3])
- fmt.Println(s1) //[[4 5]
- fmt.Println(s2) //[3 4 5 6]
- }
1.2.sort 排序
- package main
- import (
- "fmt"
- "sort"
- )
- func main() {
- num := []int{1,7,3,5,2}
- // 升序排序
- sort.Ints(num)
- fmt.Println(num) //[1 2 3 5 7]
- // 降序排序
- sort.Sort(sort.Reverse(sort.IntSlice(num)))
- fmt.Println(num) //[7 5 3 2 1]
- }
1.3. 双向链表
(1)双向链表的结构
双向链表结构中元素在内存中不是紧邻空间, 而是每个元素中存放上一个元素和后一个元素的地址
第一个元素称为 (头) 元素, 前连接 (前置指针域) 为 nil
最后一个元素称为 尾 (foot) 元素, 后连接 (后置指针域) 尾 nil
双向链表的优点
在执行新增元素或删除元素时效率高, 获取任意一个元素, 可以方便的在这个元素前后插入元素
充分利用内存空间, 实现内存灵活管理
可实现正序和逆序遍历
头元素和尾元素新增或删除时效率较高
双向链表的缺点
链表增加了元素的指针域, 空间开销比较大
遍历时跳跃性查找内容, 大量数据遍历性能低
(2)双向链表容器 List
在 Go 语言标准库的 container/list 包提供了双向链表 List
List 结构体定义如下
root 表示根元素
len 表示链表中有多少元素
- // 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
- }
其中 Element 结构体定义如下
next 表示下一个元素, 使用 Next()可以获取到
prev 表示上一个元素, 使用 Prev()可以获取到
list 表示元素属于哪个链表
Value 表示元素的值, interface()在 Go 语言中表示任意类型
- // 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. 操作 List
(1)直接使用 container/list 包下的 New()新建一个空的 List
添加, 遍历, 取首尾, 取中间元素
- package main
- import (
- "container/list"
- "fmt"
- )
- func main() {
- // 实例化
- mylist := list.New()
- fmt.Println(mylist)
- // 添加
- mylist.PushFront("a") //["a"]
- mylist.PushBack("b") //["a","b"]
- mylist.PushBack("c") //["a","b","c"]
- // 在最后一个元素的前面添加
- mylist.InsertBefore("d",mylist.Back()) //["a","b","d","c"]
- mylist.InsertAfter("e",mylist.Front()) //["a","e","b","d","c"]
- // 遍历
- for e := mylist.Front(); e != nil; e = e.Next(){
- fmt.Print(e.Value, " ") //a e b d c
- }
- fmt.Println("")
- // 取首尾
- fmt.Println(mylist.Front().Value) //a
- fmt.Println(mylist.Back().Value) //c
- // 取中间的元素, 通过不断的 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("n 的数值不对")
- }
- fmt.Println(curr.Value) //b
- }
(2)移动元素
- package main
- import (
- "container/list"
- "fmt"
- )
- func main() {
- // 实例化
- mylist := list.New()
- fmt.Println(mylist)
- // 添加
- mylist.PushFront("a") //["a"]
- mylist.PushBack("b") //["a","b"]
- mylist.PushBack("c") //["a","b","c"]
- // 在最后一个元素的前面添加
- mylist.InsertBefore("d",mylist.Back()) //["a","b","d","c"]
- mylist.InsertAfter("e",mylist.Front()) //["a","e","b","d","c"]
- // 移动, 把第一个元素一道最后一个元素的前面
- mylist.MoveBefore(mylist.Front(),mylist.Back())
- //mylist.MoveAfter(mylist.Back(),mylist.Front())
- // 把最后一个元素移动到最前面
- //mylist.MoveToFront(mylist.Back())
- // 把第一个元素移动到最后面
- //mylist.MoveToBack(mylist.Front())
- for e := mylist.Front(); e != nil; e = e.Next(){
- fmt.Print(e.Value, " ") //e b d a c
- }
- }
(3)删除
mylist.Remove(mylist.Front())
1.5. 双向循环列表
(1)循环链表特点是没有节点的指针域为 nil, 通过任何一个元素都可以找到其它元素
环形链表结构如下
双向循环链表和双向链表区别
双向循环链表没有严格意义上的头元素和尾元素
没有元素的前连接和后连接为 nil
一个长度为 n 的双向循环链表, 通过某个元素向某个方向移动, 在查找最多 n-1 次, 一定会找到另一个元素
(2)在 container/ring 包下结构体 Ring 源码如下
官方明确说明了 Ring 是循环链表的元素, 又是环形链表
实际使用时 Ring 遍历就是环形链表第一个元素
- // 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)创建和查看
- package main
- import (
- "container/ring"
- "fmt"
- )
- func main() {
- //r 代表整个循环链表, 又代表第一个元素
- 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
- // 查看元素内容
- // 循环链表有几个元素, func 就执行几次, i 当前执行元素的内容
- r.Do(func(i interface{}) {
- fmt.Print(i, " ") //0 1 2 3 4
- })
- fmt.Println("")
- // 取中间元素, 用移动
- fmt.Println(r.Move(3).Value) //3
- }
(4)增加
- package main
- import (
- "container/ring"
- "fmt"
- )
- func main() {
- //r 代表整个循环链表, 又代表第一个元素
- 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
- // 增加
- 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)删除
- package main
- import (
- "container/ring"
- "fmt"
- )
- func main() {
- //r 代表整个循环链表, 又代表第一个元素
- 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
- // 删除
- r.Unlink(1)
- r.Do(func(i interface{}) {
- fmt.Print(i, " ") //0 2 3 4
- })
- }
删除后面两个
- // 删除
- r.Unlink(2)
- r.Do(func(i interface{}) {
- fmt.Print(i, " ") //0 3 4
- })
r.Next()删除
- // 删除
- r.Next().Unlink(2)
- r.Do(func(i interface{}) {
- fmt.Print(i, " ") //0 1 4
- })qu
超出范围, 取 5 的余数
- // 删除
- r.Unlink(6)
- r.Do(func(i interface{}) {
- fmt.Print(i, " ") //0 2 3 4
- })
来源: https://www.cnblogs.com/derek1184405959/p/11298618.html