顺序表（动态数组）实现详解：从原理到接口设计（面试视角）

目录一、整体认知二、数据结构设计面试要点三、生命周期管理1. 初始化2. 销毁四、扩容机制核心深度理解面试高频1. 为什么用 realloc2. 为什么按 2 倍扩容3. 为什么用 tmp五、插入操作1. 尾插最优操作2. 头插3. 指定位置插入代码问题面试加分点六、删除操作1. 尾删2. 头删3. 指定位置删除七、时间复杂度总结八、常见面试问题1. 顺序表 vs 链表2. 为什么顺序表要扩容3. 扩容为什么不用 1九、可以继续优化的点进阶十、一句话总结面试结尾一、整体认知顺序表可以说是高级数组通过接口设计可对数组实现增删查改等操作。是重要的数据结构只是现在让我们一起感受顺序表的魅力吧核心特征底层是一段连续内存数组支持随机访问O(1)插入/删除需要挪动数据O(n)通过realloc实现动态扩容二、数据结构设计typedef int SLDateType; typedef struct SqeList { SLDateType* arr; // 指向动态数组 int size; // 当前有效元素个数 int capacity; // 当前容量 } SL;面试要点size≠capacitysize已使用空间capacity总可用空间arr NULL是初始化态三、生命周期管理1. 初始化void SLInit(SL* ps) { ps-arr NULL; ps-size ps-capacity 0; }关键点不直接分配空间懒加载思想第一次插入时再扩容2. 销毁void SLDestroy(SL* ps) { if (ps-arr) { free(ps-arr); } ps-arr NULL; ps-size ps-capacity 0; }面试关注点释放堆空间避免内存泄漏指针置空防止野指针状态重置可复用四、扩容机制核心void SLCheckCapacity(SL* ps) { if (ps-capacity ps-size) { int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity; SLDateType* tmp (SLDateType*)realloc(ps-arr, newcapacity * sizeof(SLDateType)); if (tmp NULL) { perror(realloc fail!); exit(1); } ps-arr tmp; ps-capacity newcapacity; } }深度理解面试高频1. 为什么用realloc自动处理原地扩容可能或搬迁到新地址避免手动malloc memcpy2. 为什么按 2 倍扩容保证均摊时间复杂度 O(1)避免频繁扩容3. 为什么用tmpSLDateType* tmp realloc(...)防止 realloc 失败导致原指针丢失内存泄漏五、插入操作1. 尾插最优操作void SLPushBack(SL* ps, SLDateType x) { assert(ps); SLCheckCapacity(ps); ps-arr[ps-size] x; }复杂度均摊 O(1)2. 头插void SLPushHead(SL* ps, SLDateType x) { assert(ps); SLCheckCapacity(ps); for (int i ps-size; i 0; i--) { ps-arr[i] ps-arr[i - 1]; } ps-arr[0] x; ps-size; }关键点必须从后往前移动避免覆盖时间复杂度 O(n)3. 指定位置插入void SLInsert(SL* ps, int pos, SLDateType x) { assert(ps-arr); assert(pos ps-size - 1 pos 0); SLCheckCapacity(ps); for (int i ps-size; i pos; i--) { ps-arr[i] ps-arr[i - 1]; } ps-arr[pos] x; ps-size; }代码问题面试加分点assert(pos ps-size - 1 ps 0);❌ 错误ps 0没意义指针比较插入位置应该允许pos size✅ 正确写法assert(pos 0 pos ps-size);六、删除操作1. 尾删void SLPopBack(SL* ps) { assert(ps); assert(ps-size); ps-size--; }本质逻辑删除不释放空间2. 头删void SLPopHead(SL* ps) { assert(ps); assert(ps-size); for (int i 1; i ps-size; i) { ps-arr[i - 1] ps-arr[i]; } --ps-size; }3. 指定位置删除void SLErase(SL* ps, int pos) { assert(ps-arr); assert(pos ps-size - 1 pos 0); for (int i pos; i ps-size - 1; i) { ps-arr[i] ps-arr[i 1]; } --ps-size; }七、时间复杂度总结操作时间复杂度尾插O(1)均摊头插O(n)任意插入O(n)尾删O(1)头删O(n)任意删除O(n)随机访问O(1)八、常见面试问题1. 顺序表 vs 链表维度顺序表链表内存连续离散访问O(1)O(n)插入删除O(n)O(1)已知位置cache友好高低2. 为什么顺序表要扩容数组大小固定插入时可能溢出必须动态扩展3. 扩容为什么不用 1如果每次 1插入 n 次 → realloc n 次时间复杂度退化为O(n²)九、可以继续优化的点进阶支持缩容shrink增加查找接口封装为泛型void*增加迭代器设计C方向十、一句话总结面试结尾顺序表本质是一个基于动态扩容策略的连续内存结构通过“空间换时间”实现高效访问但在插入删除上存在整体搬移的性能代价。如果你下一步想进阶我建议你做两件事把这个结构改写成C 的 vector带构造/析构/拷贝对比实现一个单链表把两者的适用场景彻底打透这两步做完你的数据结构基础就已经达到面试可用级别了。