前言

数据结构与算法的一点小笔记。

数据与内存

基本数据类型

计算机中的文本、图片、视频、语音、3D 模型等等，都是由各种基本数据类型构成的。

「基本数据类型」是 CPU 可以直接进行运算的类型，在算法中直接被使用

可分为以下四种

• 整数：根据不同的字节长度分为 byte, short, int, long
• 浮点数：代表小数，根据字节长度分为 float, double
• 字符:在计算机中是以字符集的形式保存的，char的值实际上是数字，代表字符集中的编号，计算机通过字符集查表来完成编号到字符的转换。占用空间与具体编程语言有关，通常为2 bytes 或1 byte ；
• 布尔:代表逻辑中的“是”与“否”，其占用空间需要具体根据编程语言确定，通常为 1 byte 或 1 bit

基本数据类型与数据结构的关系

数据结构是在计算机中组织与存储数据的方式，如果我们想要表示“一排数字”，自然想到使用数组。数组的存储方式可以表示数字的相邻关系、顺序关系，但至于其中存储的是整数int ，还是小数float ，或是字符char ，则与所谓的数据的结构无关了。

换言之，基本数据类型提供了数据的“内容类型”，而数据结构提供数据的“组织方式”

// 使用多种「基本数据类型」来初始化「数组」
var numbers = [5]int{}
var decimals = [5]float64{}
var characters = [5]byte{}
var booleans = [5]bool{}

计算机内存

内存和硬盘是两种主要的存储硬件设备。硬盘主要用于长期存储数据，容量较大（通常可达到 TB 级别）、速度较慢。内存用于运行程序时暂存数据，速度较快，但容量较小（通常为 GB 级别）

算法运行时，相关数据都被存储在内存中。下图展示了一个计算机内存条，其中每个黑色方块都包含一块内存空间。我们可以将内存想象成一个巨大的 Excel 表格，其中每个单元格都可以存储 1 byte 的数据，在算法运行时，所有数据都被存储在这些单元格中。

系统通过「内存地址 Memory Location」来访问目标内存位置的数据。计算机根据特定规则给表格中每个单元格编号，保证每块内存空间都有独立的内存地址。自此，程序便通过这些地址，访问内存中的数据

内存资源是设计数据结构与算法的重要考虑因素。内存是所有程序的公共资源，当内存被某程序占用时，不能被其它程序同时使用。我们需要根据剩余内存资源的情况来设计算法。例如，若剩余内存空间有限，则要求算法占用的峰值内存不能超过系统剩余内存；若运行的程序很多、缺少大块连续的内存空间，则要求选取的数据结构必须能够存储在离散的内存空间内

数据结构分类

数据结构主要可根据逻辑结构和物理结构两种角度进行分类

逻辑结构

「逻辑结构」反映了数据之间的逻辑关系，按照逻辑结构分为线性与非线性，线性表明数据在逻辑关系上是排成一条线的；而如果数据之间的逻辑关系是非线性的（例如是网状或树状的），那么就是非线性数据结构。

• 线性数据结构：数组、链表、栈、队列、哈希表；
• 非线性数据结构：树、图、堆、哈希表；

物理结构

「物理结构」反映了数据在计算机内存中的存储方式。从本质上看，分别是 数组的连续空间存储 和 链表的离散空间存储。物理结构从底层上决定了数据的访问、更新、增删等操作方法，在时间效率和空间效率方面呈现出此消彼长的特性

所有数据结构都是基于数组、或链表、或两者组合实现的。例如栈和队列，既可以使用数组实现、也可以使用链表实现，而例如哈希表，其实现同时包含了数组和链表

所有数据结构都是基于数组、或链表、或两者组合实现的。例如栈和队列，既可以使用数组实现、也可以使用链表实现，而例如哈希表，其实现同时包含了数组和链表。

• 基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量等；
• 基于链表可实现：栈、队列、哈希表、树、堆、图等；

基于数组实现的数据结构也被称为「静态数据结构」，这意味着该数据结构在在被初始化后，长度不可变。相反地，基于链表实现的数据结构被称为「动态数据结构」，该数据结构在被初始化后，我们也可以在程序运行中修改其长度。

数组与链表是其他所有数据结构的“底层积木”，重中之重。

数组Array

数组Array是一种将 相同类型元素 存储在 连续内存空间 的数据结构，将元素在数组中的位置称为元素的索引Index

数组初始化。一般会用到无初始值、给定初始值两种写法，可根据需求选取。在不给定初始值的情况下，一般所有元素会被初始化为默认值0

/* 初始化数组 */
var arr [5]int
// 在 Go 中，指定长度时（[5]int）为数组，不指定长度时（[]int）为切片
// 由于 Go 的数组被设计为在编译期确定长度，因此只能使用常量来指定长度
// 为了方便实现扩容 extend() 方法，以下将切片（Slice）看作数组（Array）
nums := []int{1, 3, 2, 5, 4}

数组优点

在数组中访问元素非常高效。这是因为在数组中，计算元素的内存地址非常容易。给定数组首个元素的地址、和一个元素的索引，利用以下公式可以直接计算得到该元素的内存地址，从而直接访问此元素。

访问元素的高效性带来了许多便利。例如，我们可以在 O(1) 时间内随机获取一个数组中的元素

/* 随机返回一个数组元素 */
func randomAccess(nums []int) (randomNum int) {
    // 在区间 [0, nums.length) 中随机抽取一个数字
    randomIndex := rand.Intn(len(nums))
    // 获取并返回随机元素
    randomNum = nums[randomIndex]
    return
}

数组缺点

数组在初始化后长度不可变。由于系统无法保证数组之后的内存空间是可用的，因此数组长度无法扩展。而若希望扩容数组，则需新建一个数组，然后把原数组元素依次拷贝到新数组，在数组很大的情况下，这是非常耗时的

/* 扩展数组长度 */
func extend(nums []int, enlarge int) []int {
    // 初始化一个扩展长度后的数组
    res := make([]int, len(nums)+enlarge)
    // 将原数组中的所有元素复制到新数组
    for i, num := range nums {
        res[i] = num
    }
    // 返回扩展后的新数组
    return res
}

数组中插入或删除元素效率低下。如果我们想要在数组中间插入一个元素，由于数组元素在内存中是“紧挨着的”，它们之间没有空间再放任何数据。因此，我们不得不将此索引之后的所有元素都向后移动一位，然后再把元素赋值给该索引

/* 在数组的索引 index 处插入元素 num */
func insert(nums []int, num int, index int) {
    // 把索引 index 以及之后的所有元素向后移动一位
    for i := len(nums) - 1; i > index; i-- {
        nums[i] = nums[i-1]
    }
    // 将 num 赋给 index 处元素
    nums[index] = num
}

删除元素也是类似，如果我们想要删除索引 (i) 处的元素，则需要把索引 (i) 之后的元素都向前移动一位。值得注意的是，删除元素后，原先末尾的元素变得“无意义”了，我们无需特意去修改它

/* 删除索引 index 处元素 */
func remove(nums []int, index int) {
    // 把索引 index 之后的所有元素向前移动一位
    for i := index; i < len(nums)-1; i++ {
        nums[i] = nums[i+1]
    }
}

总结来看，数组的插入与删除操作有以下缺点：

• 时间复杂度高：数组的插入和删除的平均时间复杂度均为 O(N) ，其中 (N) 为数组长度。
• 丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会被丢失。
• 内存浪费：我们一般会初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是我们不关心的，但这样做同时也会造成内存空间的浪费

数组常用操作

数组遍历。以下介绍两种常用的遍历方法。

/* 遍历数组 */
func traverse(nums []int) {
    count := 0
    // 通过索引遍历数组
    for i := 0; i < len(nums); i++ {
        count++
    }
    count = 0
    // 直接遍历数组
    for range nums {
        count++
    }
}

数组查找。通过遍历数组，查找数组内的指定元素，并输出对应索引。

/* 在数组中查找指定元素 */
func find(nums []int, target int) (index int) {
    index = -1
    for i := 0; i < len(nums); i++ {
        if nums[i] == target {
            index = i
            break
        }
    }
    return
}

数组应用

随机访问。如果我们想要随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现样本的随机抽取。

二分查找。例如前文查字典的例子，我们可以将字典中的所有字按照拼音顺序存储在数组中，然后使用与日常查纸质字典相同的“翻开中间，排除一半”的方式，来实现一个查电子字典的算法。

深度学习。神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。

链表

内存空间是所有程序的公共资源，排除已占用的内存，空闲内存往往是散落在内存各处的。我们知道，存储数组需要内存空间连续，当我们需要申请一个很大的数组时，系统不一定存在这么大的连续内存空间。而链表则更加灵活，不需要内存是连续的，只要剩余内存空间大小够用即可

「链表 Linked List」是一种线性数据结构，其中每个元素都是单独的对象，各个元素（一般称为结点）之间通过指针连接。由于结点中记录了连接关系，因此链表的存储方式相比于数组更加灵活，系统不必保证内存地址的连续性

链表的「结点 Node」包含两项数据，一是结点「值 Value」，二是指向下一结点的「指针 Pointer」（或称「引用 Reference」）

/* 链表结点结构体 */
type ListNode struct {
    Val  int       // 结点值
    Next *ListNode // 指向下一结点的指针（引用）
}

// NewListNode 构造函数，创建一个新的链表
func NewListNode(val int) *ListNode {
    return &ListNode{
        Val:  val,
        Next: nil,
    }
}

尾结点指向什么？ 我们一般将链表的最后一个结点称为「尾结点」，其指向的是「空」，在 Java / C++ / Python 中分别记为 null / nullptr / None 。

链表初始化方法。建立链表分为两步，第一步是初始化各个结点对象，第二步是构建引用指向关系。完成后，即可以从链表的首个结点（即头结点）出发，访问其余所有的结点。

通常将头结点当作链表的代称，例如头结点 head 和链表 head 实际上是同义的。

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个结点
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)

// 构建引用指向
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4

链表优点

在链表中，插入与删除结点的操作效率高。比如，如果我们想在链表中间的两个结点 A , B 之间插入一个新结点 P ，我们只需要改变两个结点指针即可，时间复杂度为 O(1) ，相比数组的插入操作高效很多。

/* 在链表的结点 n0 之后插入结点 P */
func insertNode(n0 *ListNode, P *ListNode) {
    n1 := n0.Next
    n0.Next = P
    P.Next = n1
}

在链表中删除结点也很方便，只需要改变一个结点指针即可。如下图所示，虽然在完成删除后结点 P 仍然指向 n2 ，但实际上 P 已经不属于此链表了，因为遍历此链表是无法访问到 P 的

/* 删除链表的结点 n0 之后的首个结点 */
func removeNode(n0 *ListNode) {
    if n0.Next == nil {
        return
    }
    // n0 -> P -> n1
    P := n0.Next
    n1 := P.Next
    n0.Next = n1
}

链表缺点

链表访问结点效率低。上节提到，数组可以在 O(1) 时间下访问任意元素，但链表无法直接访问任意结点。这是因为计算机需要从头结点出发，一个一个地向后遍历到目标结点。例如，倘若想要访问链表索引为 index （即第 index + 1 个）的结点，那么需要 index 次访问操作

/* 访问链表中索引为 index 的结点 */
func access(head *ListNode, index int) *ListNode {
    for i := 0; i < index; i++ {
        if head == nil {
            return nil
        }
        head = head.Next
    }
    return head
}

链表的内存占用多。链表以结点为单位，每个结点除了保存值外，还需额外保存指针（引用）。这意味着同样数据量下，链表比数组需要占用更多内存空间

链表常用操作

遍历链表查找。遍历链表，查找链表内值为 target 的结点，输出结点在链表中的索引

/* 在链表中查找值为 target 的首个结点 */
func findNode(head *ListNode, target int) int {
    index := 0
    for head != nil {
        if head.Val == target {
            return index
        }
        head = head.Next
        index++
    }
    return -1
}

常见链表类型

单向链表。即上述介绍的普通链表。单向链表的结点有「值」和指向下一结点的「指针（引用）」两项数据。我们将首个结点称为头结点，尾结点指向 null 。

环形链表。如果我们令单向链表的尾结点指向头结点（即首尾相接），则得到一个环形链表。在环形链表中，我们可以将任意结点看作是头结点。

双向链表。单向链表仅记录了一个方向的指针（引用），在双向链表的结点定义中，同时有指向下一结点（后继结点）和上一结点（前驱结点）的「指针（引用）」。双向链表相对于单向链表更加灵活，即可以朝两个方向遍历链表，但也需要占用更多的内存空间

/* 双向链表结点结构体 */
type DoublyListNode struct {
    Val  int             // 结点值
    Next *DoublyListNode // 指向后继结点的指针（引用）
    Prev *DoublyListNode // 指向前驱结点的指针（引用）
}

// NewDoublyListNode 初始化
func NewDoublyListNode(val int) *DoublyListNode {
    return &DoublyListNode{
        Val:  val,
        Next: nil,
        Prev: nil,
    }
}

列表List

由于长度不可变，数组的实用性大大降低。在很多情况下，我们事先并不知道会输入多少数据，这就为数组长度的选择带来了很大困难。长度选小了，需要在添加数据中频繁地扩容数组；长度选大了，又造成内存空间的浪费。

为了解决此问题，诞生了一种被称为「列表 List」的数据结构。列表可以被理解为长度可变的数组，因此也常被称为「动态数组 Dynamic Array」。列表基于数组实现，继承了数组的优点，同时还可以在程序运行中实时扩容。在列表中，我们可以自由地添加元素，而不用担心超过容量限制。

列表常用操作

初始化列表。我们通常会使用到“无初始值”和“有初始值”的两种初始化方法。

/* 初始化列表 */
// 无初始值
list1 := []int
// 有初始值
list := []int{1, 3, 2, 5, 4}

访问与更新元素。列表的底层数据结构是数组，因此可以在 O(1) 时间内访问与更新元素，效率很高。

/* 访问元素 */
num := list[1]  // 访问索引 1 处的元素

/* 更新元素 */
list[1] = 0     // 将索引 1 处的元素更新为 0

在列表中添加、插入、删除元素。相对于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为 O(1) ，但是插入与删除元素的效率仍与数组一样低，时间复杂度为 O(N)

/* 清空列表 */
list = nil

/* 尾部添加元素 */
list = append(list, 1)
list = append(list, 3)
list = append(list, 2)
list = append(list, 5)
list = append(list, 4)

/* 中间插入元素 */
list = append(list[:3], append([]int{6}, list[3:]...)...) // 在索引 3 处插入数字 6

/* 删除元素 */
list = append(list[:3], list[4:]...) // 删除索引 3 处的元素

遍历列表。与数组一样，列表可以使用索引遍历，也可以使用 for-each 直接遍历

/* 通过索引遍历列表 */
count := 0
for i := 0; i < len(list); i++ {
    count++
}

/* 直接遍历列表元素 */
count = 0
for range list {
    count++
}

拼接两个列表。再创建一个新列表 list1 ，我们可以将其中一个列表拼接到另一个的尾部

/* 拼接两个列表 */
list1 := []int{6, 8, 7, 10, 9}
list = append(list, list1...)  // 将列表 list1 拼接到 list 之后