社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
对于拿着锤子的人来讲,全世界都是钉子。-- by 查理·芒格
任何数据结构,自身特点和适用场景都非常鲜明,上面介绍的都是 Go 语言原生的数据结构,使用起来也都很方便。能否用好,取决于大家对其内部原理机制的理解是否足够深刻。
数组的长度是固定的,切片是可变长的。
数组的长度在声明它的时候就必须给定,并且之后不会再改变。可以说,数组的长度是其类型的一部分。比如,[1]string和[2]string就是两个不同的数组类型。
[3]string{"a","b","c"} // 数组 array
切片的类型字面量中只有元素的类型,而没有长度。切片的长度可以自动地随着其中元素数量的增长而增长,但不会随着元素数量的减少而减小。
[]string{"a","b","c"} // 切片 slice
切片看做是对数组的一层简单的封装,因为在每个切片的底层数据结构中,一定会包含一个数组。
数组可以被叫做切片的底层数组,切片也可以被看作是对数组的某个连续片段的引用。
从传递成本的角度讲,引用类型的值往往要比值类型的值低很多。
len
,获取数组和切片的长度。cap
,获取数组和切片的容量。接下来我们来看代码
package main
import "fmt"
func main() {
s1 := make([]int, 5)
printSlice(s1)
s2 := make([]int, 5, 8)
printSlice(s2)
}
func printSlice(s []int) {
fmt.Printf("len=%d cap=%d value:%vn", len(s), cap(s), s)
}
执行结果:
len=5 cap=5 value:[0 0 0 0 0]
len=5 cap=8 value:[0 0 0 0 0]
make
函数初始化切片时,如不指明其容量,那么容量就会和长度一致。
下面我们来看一段更加典型的代码:
func main() {
s2 := make([]int, 5, 8)
printSlice(s2)
s2 = append(s2, 6)
s2 = append(s2, 7)
s2 = append(s2, 8)
printSlice(s2)
s2 = append(s2, 9)
printSlice(s2)
}
func printSlice(s []int) {
fmt.Printf("len=%d cap=%d value:%vn", len(s), cap(s), s)
}
执行结果:
len=5 cap=8 value:[0 0 0 0 0]
len=8 cap=8 value:[0 0 0 0 0 6 7 8]
len=9 cap=16 value:[0 0 0 0 0 6 7 8 9]
这段代码说明什么问题呢?
扩容的内部原理:
关于扩容的2倍问题:
下面通过代码进行切片操作
func main() {
s3 := []int{1, 2, 3, 4, 5, 6, 7, 8}
s4 := s3[3:6] // [0] notice: [3, 6)
printSlice(s4)
s := s3[:0] // [1] 截取切片使其长度为 0
printSlice(s)
s = s3[:4] // [2] 拓展其长度
printSlice(s)
s = s3[2:] // [3] 舍弃前两个值
printSlice(s)
}
func printSlice(s []int) {
fmt.Printf("len=%d cap=%d value:%vn", len(s), cap(s), s)
}
执行结果:
len=3 cap=5 value:[4 5 6]
len=0 cap=8 value:[]
len=4 cap=8 value:[1 2 3 4]
len=6 cap=6 value:[3 4 5 6 7 8]
对以上内容,画图分析
继续看代码
func main() {
slice1 := []int{1, 2, 3, 4, 5}
slice2 := []int{6, 7, 8}
slice3 := []int{9, 10, 11}
copy(slice2, slice1) // [4]
printSlice(slice2)
copy(slice1, slice3) // [5]
printSlice(slice1)
}
func printSlice(s []int) {
fmt.Printf("len=%d cap=%d value:%vn", len(s), cap(s), s)
}
执行结果:
len=3 cap=3 value:[1 2 3]
len=5 cap=5 value:[9 10 11 4 5]
解析:如果两个切片不一样大,会按其中较小的那个数组切片的元素个数进行复制。
代码[4]中,copy(slice2, slice1)
,只会复制slice1的前3个元素到slice2中
代码[5]中,copy(slice1, slice3)
,只会复制slice3的3个元素到slice1的前3个位置
切片本身有着占用内存少和创建便捷等特点,它本质上还是数组。
删除切片中的元素是很麻烦的,涉及到元素复制、移动、槽位清空,否则还会内存泄漏。
切片频繁扩容,底层会进行内存分配和元素复制,影响性能。
当我们没有一个合理、有效的”缩容“策略的时候,旧的底层数组无法被回收,新的底层数组中也会有大量无用的元素槽位。过度的内存浪费不但会降低程序的性能,还可能会使内存溢出并导致程序崩溃。
Go 语言的链表实现在标准库的container/list
代码包中。
代码包中有两个公开的程序实体: List
和Element
,List
实现了一个双向链表(以下简称链表),Element
则代表了链表中元素的结构。
// type Element
type Element struct {
// 在元素中存储的值
Value interface{}
}
// 返回该元素的下一个元素,如果没有下一个元素则返回nil
func (e *Element) Next() *Element
// 返回该元素的前一个元素,如果没有前一个元素则返回nil。
func (e *Element) Prev() *Element
// type List
// 返回一个初始化的list
func New() *List
// 获取list l的最后一个元素
func (l *List) Back() *Element
// 获取list l的第一个元素
func (l *List) Front() *Element
// list l初始化或者清除list l
func (l *List) Init() *List
// 在list l中元素mark之后插入一个值为v的元素,并返回该元素,如果mark不是list中元素,则list不改变。
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
// 在list l中元素mark之前插入一个值为v的元素,并返回该元素,如果mark不是list中元素,则list不改变。
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
// 获取list l的长度
func (l *List) Len() int
// 将元素e移动到元素mark之后,如果元素e或者mark不属于list l,或者e==mark,则list l不改变。
func (l *List) MoveAfter(e, mark *Element)
// 将元素e移动到元素mark之前,如果元素e或者mark不属于list l,或者e==mark,则list l不改变。
func (l *List) MoveBefore(e, mark *Element)
// 将元素e移动到list l的末尾,如果e不属于list l,则list不改变。
func (l *List) MoveToBack(e *Element)
// 将元素e移动到list l的首部,如果e不属于list l,则list不改变。
func (l *List) MoveToFront(e *Element)
// 在list l的末尾插入值为v的元素,并返回该元素。
func (l *List) PushBack(v interface{}) *Element
// 在list l的尾部插入另外一个list,其中l和other可以相等。
func (l *List) PushBackList(other *List)
// 在list l的首部插入值为v的元素,并返回该元素。
func (l *List) PushFront(v interface{}) *Element
// 在list l的首部插入另外一个list,其中l和other可以相等。
func (l *List) PushFrontList(other *List)
// 如果元素e属于list l,将其从list中删除,并返回元素e的值。
func (l *List) Remove(e *Element) interface{}
代码示例:
package main
import (
"container/list"
"fmt"
)
func main() {
l := list.New() //创建一个新的list
for i := 1; i < 5; i++ {
l.PushBack(i)
}
l.PushFront(0)
printList(l) //01234
l.MoveBefore(l.Front().Next(), l.Front()) //将 e 放到 mark 前面
printList(l) //10234
l.MoveAfter(l.Front(), l.Front().Next()) //将 e 放到 mark 后面
printList(l) //01234
l.MoveToFront(l.Back()) //将尾部元素移动到首部
printList(l) //40123
l.MoveToBack(l.Front()) //将首部元素移动到尾部
printList(l) //01234
fmt.Println(l.Front().Value) //输出首部元素的值,0
fmt.Println(l.Back().Value) //输出尾部元素的值,4
l.InsertBefore(6, l.Front()) //首部元素之后插入一个值为6的元素
printList(l) //601234
l.InsertAfter(9, l.Front()) //首部元素之后插入一个值为9的元素
printList(l) //6901234
l.Init() //清空list
fmt.Print(l.Len()) //0
printList(l) //无内容
for i := 0; i < 5; i++ {
l.PushBack(i)
}
printList(l) //01234
l2 := list.New()
l2.PushBack(8)
l2.PushBackList(l) //将l中元素放在l2的末尾
printList(l2) //801234
l3 := list.New()
l3.PushFront(8)
l3.PushFrontList(l) //将l中元素放在l3的前面
printList(l3) //012348
}
func printList(l *list.List) {
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value)
}
fmt.Println("")
}
List和Element都是结构体类型。
零值就是只做了声明,但还未做初始化的变量被给予的缺省值,每个类型的零值都会依据该类型的特性而被设定。
例如:
var a [2]int // 声明的变量a的值,将会是一个包含了两个0的整数数组
var s []int // 声明的变量s的值将会是一个[]int类型的、值为nil的切片
var l list.List // [6] 声明的变量l的值将会是什么呢?这个零值将会是一个长度为0的链表。
以上代码[6]中,链表持有的根元素也是一个空壳,其中只会包含缺省的内容。
[6]中
l
可以直接拿来使用,我们称为“开箱即用”
做到开箱即用的关键在于它的延迟初始化机制
延迟初始化,可以理解为把初始化操作延后,仅在实际需要的时候才进行。
优点:分散初始化操作带来的计算量和存储空间消耗。
延迟初始化的缺点恰恰也在于“延后”。如果在调用链表的每个方法的时候,都需要先去判断链表是否已经被初始化,这会是一个计算量上的浪费。在这些方法被非常频繁地调用的情况下,这种浪费的影响就开始显现了,程序的性能将会降低。
链表实现中,一些方法是无需对是否初始化做判断的,举例如下:
List利用了自身以及Element在结构上的特点,巧妙地平衡了延迟初始化的优缺点,使得链表可以开箱即用,并且在性能上达到最优。
// Ring表示环形链表中的元素。
type Ring struct {
Value interface{} // Value类型为interface{},因此可以接受任意类型
}
// 创建一个长度为n的环形链表
func New(n int) *Ring
// 针对环形链表中的每一个元素x进行f(x)操作
func (r *Ring) Do(f func(interface{}))
// 获取环形链表长度
func (r *Ring) Len() int
// 如果r和s在同一环形链表中,则删除r和s之间的元素,
// 被删除的元素组成一个新的环形链表,返回值为该环形链表的指针(即删除前,r->Next()表示的元素)
// 如果r和s不在同一个环形链表中,则将s插入到r后面,返回值为
// 插入s后,s最后一个元素的下一个元素(即插入前,r->Next()表示的元素)
func (r *Ring) Link(s *Ring) *Ring
// 移动 n % r.Len() 个位置,n正负均可
func (r *Ring) Move(n int) *Ring
// 返回下一个元素
func (r *Ring) Next() *Ring
// 返回前一个元素
func (r *Ring) Prev() *Ring
// 删除r后面的 n % r.Len() 个元素
func (r *Ring) Unlink(n int) *Ring
代码示例:
package main
import (
"container/ring"
"fmt"
)
func main() {
const rLen = 3
r := ring.New(rLen)
for i := 0; i < rLen; i++ {
r.Value = i
r = r.Next()
}
fmt.Printf("Length of ring: %dn", r.Len()) // Length of ring: 3
// 匿名函数
printRing := func(v interface{}) {
fmt.Print(v, " ")
}
r.Do(printRing) // 0 1 2
fmt.Println()
// r之后的第二个元素乘2
r.Move(2).Value = r.Move(2).Value.(int) * 2
r.Do(printRing) // 0 1 4
fmt.Println()
fmt.Printf("r.Value: %dn", r.Value.(int)) // 0
fmt.Printf("r.Next().Value: %dn", r.Next().Value.(int)) // 1
fmt.Printf("r.Prev().Value: %dn", r.Prev().Value.(int)) // 4
// 删除r之后的2个元素,返回被删除元素组成的Ring的指针给result
result := r.Unlink(2)
r.Do(printRing) // 0
fmt.Println()
result.Do(printRing) // 1 4
fmt.Println()
}
一个链表所占用的内存空间,往往要比包含相同元素的数组所占内存大得多。
这是由于链表的元素并不是连续存储的,相邻的元素之间需要互相保存对方的指针。
不但如此,每个元素还存有它所属链表的指针。
有了这些关联,链表的结构反倒更简单了,它只持有头部元素(或称为根元素)基本上就可以了。为了防止不必要的遍历和计算,链表的长度记录在内。
# Reference
极客时间 - Go语言核心36讲
https://blog.csdn.net/u011304970/article/details/72830017
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!