1. 数组（Array）

问题：需要按索引快速存取一组元素。

核心：元素在内存中连续存储，通过 基地址 + 索引 × 元素大小 直接算出地址，实现 O(1) 随机访问。

特点

内存连续分配
支持 O(1) 按索引访问
插入/删除需要移动元素，O(n)

优点

随机访问极快，缓存友好（CPU 预读连续内存）
实现简单，几乎所有语言内置

缺点

静态数组大小固定，动态数组扩容需要复制
中间插入/删除 O(n)，效率低
需要大块连续内存，分配可能失败

// JS 的 Array 就是动态数组
const arr = [1, 2, 3, 4, 5];

// O(1) 随机访问
console.log(arr[2]); // 3

// O(1) 尾部插入（均摊）
arr.push(6);

// O(n) 中间插入
arr.splice(2, 0, 99); // [1, 2, 99, 3, 4, 5, 6]

// O(n) 删除
arr.splice(2, 1);

package main

func main() {
    // Go 切片 = 动态数组
    arr := []int{1, 2, 3, 4, 5}

    // O(1) 随机访问
    _ = arr[2] // 3

    // O(1) 尾部插入（均摊）
    arr = append(arr, 6)

    // O(n) 中间插入
    arr = append(arr[:2], append([]int{99}, arr[2:]...)...)
    // [1 2 99 3 4 5 6]

    // O(n) 删除（删除索引2）
    arr = append(arr[:2], arr[3:]...)
}

JS 的 Array 底层在 V8 中是动态数组（类似 std::vector）；Go 的切片也是动态数组，append 超过容量时会自动扩容。