常用数据结构

上一篇我们学了函数和指针，知道了切片和 map 作为参数时是引用语义。这篇是整个 Go 教程中最重要的一篇——我们要学习 Go 语言中常用的数据结构。

算法题的本质就是对数据结构进行操作，如果你不熟悉这些数据结构的基本用法，看算法代码就会一头雾水。好消息是，Go 的数据结构用起来很直观，你不需要记住所有 API，只需要掌握最常用的那几个操作就够了。用多了自然就记住了，忘了随时可以回来查。

¶数组与切片

¶数组（了解即可）

Go 的数组长度是固定的，声明时必须指定大小：

数组在实际开发中很少用，因为它的长度是固定的，不能动态增减。在 Go 里，我们几乎都用切片（slice）来代替数组，切片可以理解为"可变长度的数组"。

¶切片基础

切片是 Go 中最常用的数据结构，没有之一。它的类型写作 []int（注意方括号里没有数字），可以动态增长。

len 和 cap 的区别：len 是切片当前有多少个元素，cap 是底层数组能容纳多少个元素。当 append 导致元素个数超过容量时，Go 会自动分配更大的底层数组。日常使用只关注 len 就行，cap 一般不用管。

¶切片的增删操作

切片的增删是刷题时最常用的操作，重点掌握 append 和切片截取。

重点说一下删除元素的技巧：append(nums[:i], nums[i+1:]...) 的意思是——把索引 i 前面的部分和索引 i 后面的部分拼起来，跳过了索引 i 的元素，就相当于删除了它。

注意末尾的 ... 是展开运算符，把切片展开成一个个元素传给 append。

¶二维切片

二维切片在表示矩阵、网格时非常常用。Go 没有内置的二维切片语法，需要手动创建：

创建二维切片的套路是固定的：先 make 外层切片，然后循环 make 每一行。这个写法虽然比一些语言啰嗦，但逻辑很清晰。

¶字符串

¶字符串基础

Go 的字符串有一个重要特点：不可变。一旦创建就不能修改其中的某个字符，想要修改就得转成 []byte 或 []rune。

注意 len(s) 返回的是字节数，不是字符数。对于纯 ASCII 字符串（英文、数字）这没区别，但对于包含中文的字符串就不同了——一个中文字符通常占 3 个字节。

¶[]byte 与 []rune 转换

既然字符串不可变，想要修改就得先转换。Go 提供了两种转换方式：

• []byte —— 按字节转换，适合处理纯 ASCII 字符（英文字母、数字）
• []rune —— 按 Unicode 字符转换，能正确处理中文等多字节字符

简单记：处理英文用 []byte，处理中文用 []rune。刷算法题的时候，如果题目说"字符串只包含小写英文字母"，用 []byte 就够了。

¶strings 包常用函数

Go 的 strings 包提供了很多字符串操作函数，刷题时经常用到：

¶strconv 包：字符串和数字互转

算法题中经常需要把字符串转成数字、或者把数字转成字符串，用 strconv 包：

日常刷题最常用的就是 strconv.Atoi（字符串转数字）和 strconv.Itoa（数字转字符串），这两个记住就够了。注意 Atoi 会返回两个值，第二个是错误信息，如果确定输入一定是合法数字，可以用 _ 忽略错误。

¶结构体

¶定义与使用

Go 没有类（class）的概念，但有结构体（struct），可以把多个字段打包在一起。在算法题中，结构体常用来表示图的节点、树的节点等。

¶结构体指针

用 & 取结构体的地址得到指针。Go 有一个很贴心的设计：通过指针访问字段不需要写 (*p).Name，直接写 p.Name 就行，编译器会自动解引用。

&Point{X: 3, Y: 4} 是 Go 中创建结构体指针最常见的写法，在算法题中经常看到。比如链表节点 &ListNode{Val: 1} 就是这个套路。

¶哈希表 map

map 是 Go 中最常用的数据结构之一，存储键值对，增删查改都很快。这里只讲用法，关于哈希表的底层原理，后面的 哈希表核心原理 会详细讲解。

¶常用操作

¶判断 key 是否存在

这是 Go 的经典写法，几乎每道用到 map 的算法题都会出现：

val, ok := m[key] 这个写法叫做"comma ok"惯用法。ok 是一个布尔值，为 true 说明 key 存在，为 false 说明不存在。如果你不关心 key 是否存在，直接 val := m[key] 也行，不存在时 val 就是零值（数字类型是 0，字符串是 ""）。

注意频率统计时 freq[text[i]]++ 这个写法：即使 key 不存在，map 取值也会返回零值 0，加 1 之后就是 1，所以不需要先判断 key 是否存在。

¶哈希集合

Go 没有内置的 Set 类型，但可以用 map 来模拟。惯用写法是 map[T]struct{}，其中 struct{} 是空结构体，不占用任何内存。

你可能觉得 struct{}{} 这个写法很奇怪——struct{} 是类型，struct{}{} 是这个类型的一个值（空结构体的字面量）。虽然写起来有点啰嗦，但这是 Go 社区公认的 Set 惯用法。

如果你觉得 struct{}{} 太丑，也可以用 map[int]bool 来代替，value 统一设成 true：

set := make(map[int]bool)
set[1] = true
set[2] = true
if set[99] {
    // 不会执行，因为不存在的 key 返回 false
}

map[int]bool 写起来更简洁，但会多占一点点内存（每个 value 占 1 字节）。刷题时两种都行，选你觉得顺手的。

¶栈（用切片模拟）

Go 标准库没有内置栈，但用切片就能轻松模拟——入栈用 append，出栈用切片截取。关于栈和队列的底层原理，后面的 队列/栈基本原理 会详细讲解，这里先学会怎么用就行：

栈的操作总结：

• 入栈：stack = append(stack, x)
• 栈顶：stack[len(stack)-1]
• 出栈：stack = stack[:len(stack)-1]
• 判空：len(stack) == 0

这四个操作在括号匹配、单调栈等算法题中用得非常多，建议记牢。

来看一个经典的栈应用——括号匹配：

¶队列

队列是先进先出（FIFO）的数据结构，在 BFS（广度优先搜索）中必用。Go 有两种方式实现队列。

¶用切片模拟（简单版）

用切片模拟队列写起来很简单，但有一个问题：queue = queue[1:] 出队时，前面的内存不会被释放，如果队列很大会浪费内存。对于算法题来说一般没问题，但如果追求效率，可以用 container/list。

¶用 container/list 模拟（推荐）

container/list 是 Go 标准库提供的双向链表，两端增删都很高效，非常适合当队列用。

container/list 的元素类型是 interface{}（任意类型），所以取值时需要用类型断言 .(int) 转成具体类型。这是它唯一不太方便的地方。

队列的操作总结：

• 入队：queue.PushBack(x)
• 队头：queue.Front().Value.(int)
• 出队：queue.Remove(queue.Front())
• 判空：queue.Len() == 0

来看一个 BFS 的例子，感受队列在实际算法中的用法：

¶小结

把这篇的数据结构和核心操作汇总一下：

不需要一次记住所有方法，用多了自然就熟了。下一篇会讲一些刷算法题时的常用技巧，比如排序、数学运算、常用的内置函数等。