动态数组的实现：用malloc玩转可变长数组

动态数组，说白了就是能自动长大的数组。C语言里普通数组的大小是编译时就定死的，你没法在程序跑起来之后说“哎，再给我加俩位置”。但实际项目中，数据量往往是运行时才知道的——比如你从网络收包，鬼知道会来多少字节？这时候就得靠动态数组了。

我个人习惯把动态数组叫做“穷人版vector”，毕竟C++里vector用起来太爽了，但C语言里我们得自己造轮子。不过别怕，这个轮子其实不难，而且造一遍之后，你对内存管理的理解会上一个台阶。

1. 动态数组的核心结构

先定义个结构体，把数组的元信息存下来：

typedef struct {
    int *data;      // 指向堆内存的指针
    size_t size;    // 当前元素个数
    size_t capacity; // 当前容量（最多能存多少个）
} DynamicArray;

这里有个关键点：size和capacity是两码事。size是实际用了多少，capacity是分配了多少空间。我见过新手把这两个混为一谈，结果扩容时直接懵逼。

2. 初始化与销毁

初始化时，我建议先分配一小块初始容量，别一上来就搞很大。比如：

DynamicArray* da_create(size_t initial_capacity) {
    DynamicArray *arr = malloc(sizeof(DynamicArray));
    if (!arr) return NULL;

    arr->data = malloc(initial_capacity * sizeof(int));
    if (!arr->data) {
        free(arr);
        return NULL;
    }

    arr->size = 0;
    arr->capacity = initial_capacity;
    return arr;
}

销毁时记得先释放data，再释放结构体本身。顺序反了你就泄漏内存了——我曾经在项目里犯过这个错，排查了半天才发现是free顺序搞反了。

void da_destroy(DynamicArray *arr) {
    if (arr) {
        free(arr->data);
        free(arr);
    }
}

3. 扩容策略：别一次只扩一个

动态数组最核心的就是扩容策略。你想想看，如果每次添加一个元素就realloc一次，那效率得多低？我建议采用倍数扩容，最常见的是2倍增长。

为什么是2倍？因为均摊下来，每次插入的时间复杂度是O(1)。如果每次只加1个，那插入n个元素就是O(n²)，数据量一大直接爆炸。

int da_append(DynamicArray *arr, int value) {
    if (arr->size >= arr->capacity) {
        // 扩容为原来的2倍
        size_t new_cap = arr->capacity * 2;
        int *new_data = realloc(arr->data, new_cap * sizeof(int));
        if (!new_data) return -1; // 扩容失败

        arr->data = new_data;
        arr->capacity = new_cap;
    }

    arr->data[arr->size++] = value;
    return 0;
}

这里有个细节：realloc可能会移动内存块，所以一定要用返回值更新指针。直接realloc(arr->data, ...)然后继续用arr->data？嗯，这是典型的坑——如果realloc失败返回NULL，你原来的指针就丢了。

4. 缩容策略：别急着缩

缩容比扩容更讲究。我见过有人每次删除元素就缩容，结果频繁realloc导致性能雪崩。正确的做法是：当size降到capacity的1/4时，才缩容到一半。这样避免了“添加-删除-添加”时的反复震荡。

int da_pop(DynamicArray *arr) {
    if (arr->size == 0) return -1;

    int val = arr->data[--arr->size];

    // 缩容条件：size <= capacity/4 且 capacity > 初始容量
    if (arr->size <= arr->capacity / 4 && arr->capacity > 4) {
        size_t new_cap = arr->capacity / 2;
        int *new_data = realloc(arr->data, new_cap * sizeof(int));
        if (new_data) { // 缩容失败也没关系，继续用旧的
            arr->data = new_data;
            arr->capacity = new_cap;
        }
    }

    return val;
}

5. 完整扩容缩容流程图

下面这张图把整个生命周期串起来了，你看一眼就能明白什么时候扩、什么时候缩：

6. 避坑指南：我踩过的三个雷

• realloc后指针没更新：我早期写代码时直接 realloc(ptr, new_size) 然后继续用ptr，结果realloc移动了内存块，ptr变成野指针。记住：ptr = realloc(ptr, new_size); 才是正确写法。
• 忘记检查realloc返回值：realloc可能返回NULL，这时候原来的内存块还在，但你没保存原指针，就泄漏了。正确做法是用临时变量接收返回值。
• 缩容太激进：有个项目里我每次pop都缩容，结果用户频繁增删时，程序卡成PPT。后来改成“1/4缩容到1/2”，世界清净了。

7. 完整代码骨架

最后给个完整的头文件声明，方便你直接复用：

// dynamic_array.h
#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H

#include <stddef.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} DynamicArray;

DynamicArray* da_create(size_t initial_capacity);
void da_destroy(DynamicArray *arr);
int da_append(DynamicArray *arr, int value);
int da_pop(DynamicArray *arr);
int da_get(const DynamicArray *arr, size_t index);
void da_set(DynamicArray *arr, size_t index, int value);

#endif

实现文件里，get和set记得做边界检查。我习惯在debug模式下用assert，release模式下返回错误码。

---

动态数组的实现，说白了就是管理好size和capacity这对兄弟。扩容时大方点（×2），缩容时保守点（1/4触发）。记住这个原则，你的动态数组就能在各种场景下跑得稳。

嗯，如果你在实际项目中遇到内存相关的诡异问题，多半是扩容缩容策略没调好。别问我怎么知道的——我曾经在一个网络库里因为缩容太频繁，导致线上服务时不时卡顿，查了两天才找到根儿。