数组的内存模型与基本操作 ​

从这一章开始，我们进入数据结构的学习。

第一个要掌握的数据结构就是数组——最简单、最基础、也是用得最多的数据结构。

数组是什么 ​

数组是一种线性数据结构，它把一组元素按顺序存放在连续的内存空间中。

两个核心特点：

1. 连续存储：元素在内存中紧挨着
2. 索引访问：通过下标直接定位元素

内存地址      值
┌─────────┬─────┐
│ 0x1000  │  10 │  arr[0]
├─────────┼─────┤
│ 0x1004  │  20 │  arr[1]
├─────────┼─────┤
│ 0x1008  │  30 │  arr[2]
├─────────┼─────┤
│ 0x100C  │  40 │  arr[3]
├─────────┼─────┤
│ 0x1010  │  50 │  arr[4]
└─────────┴─────┘

这个特性让数组拥有了一个杀手级能力：O(1) 随机访问。

数组的内存模型 ​

为什么数组能做到 O(1) 访问？

答案在于地址计算。

假设数组的起始地址是 base_address，每个元素占 element_size 字节。那么第 i 个元素的地址是：

address = base_address + i × element_size

这是一个简单的算术运算，不管数组有多大，计算地址的时间都是常数。

// 假设 arr 起始地址 0x1000，每个元素 4 字节
const arr = [10, 20, 30, 40, 50];

// arr[3] 的地址 = 0x1000 + 3 × 4 = 0x100C
// CPU 直接跳到 0x100C 读取，不需要从头遍历
console.log(arr[3]);  // 40，O(1) 时间

这也解释了一个常见问题：为什么数组索引从 0 开始？

因为索引 i 实际上是偏移量——相对于起始地址的偏移。第一个元素偏移 0 个单位，所以索引是 0。

如果从 1 开始，每次计算地址都要额外减 1，虽然只是一条指令，但对于底层数据结构来说，能省就省。

对比：链表的顺序访问 ​

链表就不一样了。链表的元素散落在内存各处，每个元素通过指针指向下一个。

要访问第 i 个元素，必须从头开始，沿着指针走 i 步。这是 O(n) 的操作。

数组的 O(1) 随机访问，是它最大的优势。

数组的基本操作与复杂度 ​

访问（Access）—— O(1) ​

const arr = [1, 2, 3, 4, 5];
const element = arr[2];  // 直接通过索引访问

不管数组多大，访问任意位置都是常数时间。

搜索（Search）—— O(n) ​

如果数组是无序的，查找一个元素只能从头到尾扫一遍：

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}
// 最坏情况：遍历整个数组，O(n)

如果数组是有序的，可以用二分查找，复杂度降到 O(log n)。这是后面会讲的内容。

插入（Insert） ​

插入的复杂度取决于插入位置。

末尾插入 —— O(1)

const arr = [1, 2, 3];
arr.push(4);  // [1, 2, 3, 4]

在末尾加一个元素，不需要移动其他元素，常数时间。

（严格来说是"均摊 O(1)"，因为可能触发扩容，后面会解释。）

开头插入 —— O(n)

const arr = [1, 2, 3];
arr.unshift(0);  // [0, 1, 2, 3]

在开头插入，所有元素都要后移一位。n 个元素，O(n) 时间。

中间插入 —— O(n)

const arr = [10, 20, 30, 40, 50];
arr.splice(2, 0, 25);  // 在索引 2 处插入 25
// 结果：[10, 20, 25, 30, 40, 50]

看一下这个过程：

原数组：[10, 20, 30, 40, 50]
               ↑ 插入点（索引 2）

步骤 1：后移元素
[10, 20, __, 30, 40, 50]  // 30, 40, 50 各后移一位

步骤 2：插入新元素
[10, 20, 25, 30, 40, 50]

需要移动 n - i 个元素，最坏情况（插入开头）是 O(n)。

删除（Delete） ​

删除和插入类似，也取决于位置。

const arr = [1, 2, 3, 4, 5];

// 末尾删除 —— O(1)
arr.pop();  // [1, 2, 3, 4]

// 开头删除 —— O(n)
arr.shift();  // [2, 3, 4]

// 中间删除 —— O(n)
arr.splice(1, 1);  // 删除索引 1 的元素

复杂度总结 ​

记住这个规律：数组擅长访问，不擅长中间插删。

静态数组 vs 动态数组 ​

在 C 语言中，数组的大小在编译时就确定了，这叫静态数组。

int arr[10];  // 只能存 10 个元素，不能多也不能少

但 JavaScript 的数组可以随意增长，这叫动态数组。

动态数组是怎么实现的？

扩容机制 ​

动态数组在内部维护一个容量（capacity）。当元素数量超过容量时，会：

1. 申请一块更大的内存（通常是原来的 2 倍）
2. 把原有元素复制过去
3. 释放旧内存

// 动态数组扩容示意（伪代码）
class DynamicArray {
    constructor() {
        this.capacity = 4;
        this.length = 0;
        this.data = new Array(this.capacity);
    }
    
    push(element) {
        // 容量不够，需要扩容
        if (this.length >= this.capacity) {
            const newCapacity = this.capacity * 2;
            const newData = new Array(newCapacity);
            
            // 复制原有元素 —— O(n)
            for (let i = 0; i < this.length; i++) {
                newData[i] = this.data[i];
            }
            
            this.data = newData;
            this.capacity = newCapacity;
        }
        
        this.data[this.length] = element;
        this.length++;
    }
}

均摊分析 ​

扩容需要 O(n) 时间，那为什么说 push 是 O(1)？

关键在于均摊。

假设初始容量是 1，连续 push n 个元素。扩容发生在第 1、2、4、8、... 个元素插入时：

• 第 1 次扩容：复制 1 个元素
• 第 2 次扩容：复制 2 个元素
• 第 3 次扩容：复制 4 个元素
• ...
• 第 k 次扩容：复制 2^(k-1) 个元素

总复制次数：1 + 2 + 4 + ... + n/2 ≈ n

n 次 push，总共复制 n 次。平均每次 push 的代价是 n/n = O(1)。

这就是**均摊 O(1)**的含义：虽然单次操作可能很慢，但平均下来是 O(1)。

JavaScript 数组的特殊性 ​

JavaScript 的数组和传统意义上的数组有些不同。

不是"真正的"数组 ​

在底层，JavaScript 数组实际上是一种特殊的对象。它的索引是字符串形式的键。

const arr = [10, 20, 30];

// 等价于
const obj = {
    '0': 10,
    '1': 20,
    '2': 30,
    length: 3
};

这带来了一些特殊行为。

可以存储不同类型 ​

const mixed = [1, 'hello', true, { a: 1 }, [1, 2, 3]];

传统数组要求元素类型一致，JavaScript 不要求。但这会影响性能——V8 引擎对同类型数组有专门的优化。

建议：在 LeetCode 刷题和实际开发中，尽量保持数组元素类型一致。

稀疏数组 ​

const sparse = [];
sparse[0] = 'a';
sparse[100] = 'b';
console.log(sparse.length);  // 101
console.log(sparse[50]);     // undefined

中间的 99 个位置是"空洞"。这叫稀疏数组。

稀疏数组在遍历时有坑：

const sparse = [1, , , 4];  // 索引 1、2 是空的

sparse.forEach(x => console.log(x));  // 只输出 1 和 4，跳过空洞
for (let i = 0; i < sparse.length; i++) {
    console.log(sparse[i]);  // 输出 1, undefined, undefined, 4
}

建议：避免使用稀疏数组，它们的行为往往出人意料。

V8 的优化 ​

好消息是，V8 引擎会根据数组的使用模式进行优化。如果数组是"正常"的（连续、同类型），V8 会把它当作真正的数组来处理，性能和 C 数组接近。

在 LeetCode 题目中，通常假设数组是"正常"的，不用担心这些 JavaScript 特性。

数组的优缺点 ​

优点 ​

1. O(1) 随机访问：通过索引直接访问任意元素
2. 内存连续，缓存友好：CPU 缓存会预加载相邻数据
3. 简单直观：概念清晰，易于使用

缺点 ​

1. 插入删除可能 O(n)：需要移动元素
2. 大小固定或扩容有开销：静态数组大小固定，动态数组扩容耗时
3. 需要预先分配内存：可能浪费空间

适用场景 ​

• 频繁随机访问
• 主要在末尾增删
• 元素数量相对固定或可预估

不适合：

• 频繁在中间/开头插删 → 考虑链表
• 元素数量变化剧烈且不可预估 → 考虑链表

本章小结 ​

这一章我们学习了数组的底层原理：

1. 连续存储：元素在内存中紧挨着
2. 地址计算：address = base + index × size，这是 O(1) 访问的关键
3. 操作复杂度：访问 O(1)，搜索 O(n)，末尾增删 O(1)，其他位置增删 O(n)
4. 动态数组：通过扩容机制实现自动增长，均摊 O(1)
5. JavaScript 特性：本质是对象，但 V8 会优化

理解数组的内存模型，是分析数组算法复杂度的基础。

下一章，我们来看数组的各种遍历模式——单指针、双指针、滑动窗口，这些是 LeetCode 数组题的核心技巧。