数组（顺序存储）基本原理#

一、数组两大分类#

静态数组：原始形态，是一块固定长度、连续的内存空间，依靠索引直接访问内存。长度初始化后不可改变。
动态数组：基于静态数组封装而来，内置 push、insert、remove 等常用 API，可自动完成扩容/缩容，简化增删操作。
- 后续栈、队列、哈希表等很多数据结构底层都依赖动态数组实现
- 算法刷题和开发日常一般直接使用动态数组（Go 的 slice），静态数组多用于理解底层原理

Go 静态数组定义#

1
// 定义长度固定为 10 的 int 静态数组
2
var arr [10]int
3
// 索引赋值
4
arr[0] = 1
5
arr[1] = 2
6
// 索引取值
7
a := arr[0]

核心特性：随机访问 — 通过索引可 O(1) 时间直接读取/修改对应元素

二、静态数组：增删原理 & 时间复杂度#

1. 新增元素#

情况1：末尾追加（有空闲空间）#

直接对末尾空位索引赋值，无需移动元素

1
var arr [10]int
2
// 前4个位置存入元素
3
for i := 0; i < 4; i++ {
4
    arr[i] = i
5
}
6
// 末尾追加元素
7
arr[4] = 4
8
arr[5] = 5

时间复杂度：O(1)

情况2：中间插入（有空闲空间）#

需要把插入位置及之后的原有元素向后整体搬移一位（倒序遍历防止数据覆盖），腾出空位后插入新元素

1
package main
2
import "fmt"
3

4
func main() {
5
    var arr [10]int
6
    for i := 0; i < 4; i++ {
7
        arr[i] = i
8
    }
9
    // 在索引 2 插入元素 666，后移后续元素
10
    for i := 4; i > 2; i-- {
11
        arr[i] = arr[i-1]
12
    }
13
    arr[2] = 666
14
    fmt.Println(arr)
15
}

时间复杂度：O(N)

情况3：数组空间已满#

需要手动扩容：新建一块更大的静态数组，复制原有全部数据，再进行新增操作

1
// 原数组已满
2
arr := make([]int, 10)
3
for i := 0; i < 10; i++ {
4
    arr[i] = i
5
}
6
// 创建更大数组并复制原数据
7
newArr := make([]int, 20)
8
for i := 0; i < 10; i++ {
9
    newArr[i] = arr[i]
10
}
11
// 在新数组末尾追加元素
12
newArr[10] = 10

扩容涉及全量拷贝，单次扩容操作复杂度：O(N)

2. 删除元素#

情况1：删除末尾元素#

直接标记/截断末尾元素，无需搬移数据

1
var arr [10]int
2
for i := 0; i < 5; i++ {
3
    arr[i] = i
4
}
5
// 删除末尾元素（示例标记为-1）
6
arr[4] = -1

时间复杂度：O(1)

情况2：删除中间元素#

把被删元素后面的元素整体向前搬移一位（正序遍历），保持数组连续性

1
var arr [10]int
2
for i := 0; i < 5; i++ {
3
    arr[i] = i
4
}
5
// 删除索引1的元素，后续元素前移
6
for i := 1; i < 4; i++ {
7
    arr[i] = arr[i + 1]
8
}
9
arr[4] = -1

时间复杂度：O(N)

3. 查 & 改#

按索引查询元素：O(1)
按索引修改元素：O(1)
按元素值遍历查找（非索引查找）：O(N)

4. 静态数组复杂度总览#

增
- 末尾追加（有空位）：O(1)
- 中间插入：O(N)
- 满数组扩容新增：O(N)
删
- 删除末尾元素：O(1)
- 删除中间元素：O(N)
查（索引访问）：O(1)
改（索引修改）：O(1)

三、动态数组（Go Slice）用法#

底层依旧依托静态数组，自动处理扩容、缩容和数据搬移，对外提供简洁 API

1
package main
2
import "fmt"
3

4
func main() {
5
    // 创建初始长度为0的动态数组
6
    arr := make([]int, 0)
7

8
    // 末尾追加元素
9
    for i := 0; i < 10; i++ {
10
        arr = append(arr, i)
11
    }
12

13
    // 在索引 2 插入元素 666
14
    arr = append(arr[:2], append([]int{666}, arr[2:]...)...)
15

16
    // 在头部插入元素 -1
17
    arr = append([]int{-1}, arr...)
18

19
    // 删除末尾元素
20
    arr = arr[:len(arr)-1]
21

22
    // 删除索引 2 的元素
23
    arr = append(arr[:2], arr[3:]...)
24

25
    // 索引查询
26
    a := arr[0]
27
    fmt.Println(a)
28

29
    // 索引修改
30
    arr[0] = 100
31

32
    // 根据值查找索引（遍历查找，复杂度 O(N)）
33
    index := -1
34
    for i, v := range arr {
35
        if v == 666 {
36
            index = i
37
            break
38
        }
39
    }
40
    fmt.Println("666的索引：", index)
41
}